算法1
二维状态转移方程代码如下
C++ 代码
#include <iostream>
using namespace std;
const int MAX = 1010;
int v[MAX], w[MAX];
int f[MAX][MAX];
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if (j < v[i]){
f[i][j] = f[i - 1][j];
}else{
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m];
}
为什么用两层for循环:因为体积不一定全用到来达到最大价值,所以第二层for循环来循环体积
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) : 在选择第i件物品的时候,f[i][j] = f[i - 1][j - v[i]] + w[i], 状态还是已经选了i-1个物品的状态,体积要减去选第i件物品所需的体积,再加上第i件物品的价值wi,与不选第i件物品比较。
算法2
一维状态转移方程
C++ 代码
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
状态f[j]定义:N 件物品,背包容量j下的最优解。
为什么for(j)循环逆序?
因为f[i][j]的状态由f[i - 1][j]得来,两者相等