• 题目
• 样例
• 思路
• 完整代码

题目

=================================================
有n种重量和价值分别为wi, vi的物品。从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值。在这里，每件物品可以挑选多次。

Input

1 <= n <= 100
1 <= wi, vi <= 100 1 <= W <= 10000

Output

价值最大值。

样例

=================================================

Sample input:

3 7 3 4 4 5 2 3

Sample output:

10

思路

=================================================

dp
在01背包的问题上稍微改动，本来三层循环可以解决，但是复杂度为O(nW2)，书上有简化方法

max{dp[i][j-kw[i]]+kv[i]|k>+0}
=max(dp[i][j], max{dp[i][j-kw[i]]+kv[i]|k>=1})
=max(dp[i][j], max{dp[i][(j-w[i])-kw[i]]+kv[i]|k>=0}+v[i])
=max(dp[i][j], dp[i+1][j-w[i]]+v[i])
最后一步实在是没看懂，微笑脸
但是如果是01背包，因为只有一件物品，我们考虑的是装入i之后，能不能装下下一件物品。但是在完全背包中，有无数件，所以考虑的是，装入后，我们所要考虑的是在当前容量下是否再装入一个物品。总而言之，是他当前的状态.[j-w[i]]的意思是至少有还保留一件w[i]的空间。总而言之，如果放入i+1,他的状态就是他自己i+1,而不是上一个i。

完整代码

=================================================

#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+5][MAX_N+5];

void solve(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= W; j++){
			if(j < w[i]){
				dp[i+1][j] = dp[i][j];
			}else{
				dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
			}
		}
	}
	cout << dp[n][W];
}

int main(){
	cin >> n >> W;
	for(int i = 0; i < n; i++){
		cin >> w[i] >> v[i];
	}
	solve();
}