背包问题是典型的动态规划例子。我们可将子问题的解存储下来，以免计算其母问题时需用到子问题结果而重复计算。
问题阐述
给定背包容量W，n个物品及各个物品的价值和重量，问如何选择使背包能装下物品的价值最大？
定义数据结构
- 背包容量W
- 物品个数n
- 各个物品价值和重量分别为v[n], w[n]
- (动态规划数组)dp[n][W]，dp[i][j]表示当背包容量达到j时，前i个物品所具有的最佳价值组和
状态转移方程
对第i个物品的判断，有两种可能性：
- 该物品重量大于当前背包容量，则dp[i][j] = dp[i-1][j]
-
该物品重量小于当前背包容量时，并不是无脑加入，而需要判断加入该物品后背包容量剩余j-w[j]时的价值是否会比不加入物品i大
那么可写出如下状态转移方程：
状态转移方程
考虑下面这个问题
代码实现
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 105;
int v[maxn], w[maxn], dp[maxn];
int main()
{
int n; cin >> n;
int W; cin >> W;
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
memset(dp, 0, sizeof(dp));
for(int i=1; i<=n; i++)
cin >> w[i] >> v[i];
for(int i=1; i<=n; i++){
int ww = W;
for(; ww>=w[i]; ww--){ //注意是从大到小的顺序
dp[ww] = max(dp[ww], dp[ww-w[i]]+v[i]); //递推公式
}
}
cout << dp[W];
return 0;
}
Tips
- 背包的每个剩余容量均对应一个物品最优价值
- 按背包容量的降序动态规划
