一个背包总容量为bagSize,现在有len个物品,第i个 物品体积为weight[i],价值为value[i],现在往背包里面装东西,怎么装能使背包的内物品价值最大?
用一个数组f[i-1][j]表示在只有i-1个物品,容量为j的情况下背包问题的最优解,那么当物品种类变大为i时,最优解是什么?第i个物品可以选择放进背包或者不放进背包(这也就是0和1),假设放进背包(前提是放得下,即weight[i]<=j),那么f[i][j]=f[i][j-weight[i]+value[i];如果不放进背包,那么f[i][j]=f[i-1][j]。
即状态转移方程:f[i][j]=max(f[i-1][j],f[i][j-weight[i]+value[i](weight[i]<=j))。
本题的代码如下:
#include<iostream> #include<algorithm> using namespace std; int Get01PackageAnswer(int *weight,int *value,int len,int bagSize); int main() { int len; cin >> len; int arr[50] = { 0 }; int tmp; int sum = 0; for (int i = 0; i < len; i++) { cin >> tmp; arr[i] = tmp / 1024; sum += arr[i]; } int bagSize = sum / 2; int maxTime = Get01PackageAnswer(arr,arr,len,bagSize); cout << max(maxTime, sum - maxTime) * 1024; return 0; } int Get01PackageAnswer(int *weight, int *value, int len, int bagSize) { int **f = new int*[len+1]; for (int i = 0; i < len+1; i++) { f[i] = new int[bagSize+1]; } for (int j = 0; j <= bagSize; j++) { for (int i = 0; i <= len; i++) { if (i == 0 || j == 0) { f[i][j] = 0; } else if (j < weight[i-1]) { f[i][j] = f[i-1][j]; } else { f[i][j] = max((f[i-1][j-weight[i-1]]+value[i-1]),(f[i-1][j])); } } } return f[len][bagSize]; }