1.题目解析

题目来源

[模版]完全背包_牛客题霸_牛客

测试用例 

2.算法原理

1.状态表示

与01背包相同，这里的完全背包也是需要一个二维dp表来表示最大价值，具体如下

求最大价值dp[i][j]:在[1,i]区间选择物品，此时总体积不大于j时的最大价值

求装满时的价值dp[i][j]:在[1,i]区间选择物品，此时总体积严格等于j时的价值

2.状态转移方程

3.初始化

4.填表顺序

从上至下，每一行从左到右

5.返回值 

返回最后一个位置dp表的值

3.实战代码

#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int n,V;
int v[N];
int w[N];int main()
{cin>>n>>V;for(int i = 1;i <= n;i++){cin>>v[i]>>w[i];}for(int i = 1;i <= n;i++){for(int j = 0;j <= V;j++){dp[i][j] = dp[i-1][j];if(j >= v[i]){dp[i][j] = max(dp[i][j],dp[i][j-v[i]] + w[i]);}}}cout<<dp[n][V]<<endl;memset(dp,0,sizeof(dp));for(int j = 1;j <= V;j++){dp[0][j] = -1;}for(int i = 1;i <= n;i++){for(int j = 0;j <= V;j++){dp[i][j] = dp[i-1][j];if(j >= v[i] && dp[i][j-v[i]] != -1){dp[i][j] = max(dp[i][j],dp[i][j-v[i]] + w[i]);}}}cout<<(dp[n][V] == -1 ? 0 : dp[n][V])<<endl;return 0;
}

代码解析 

4.代码优化