【01背包问题】

xiao-gan 2021-09-05 原文

思路：

维持一个数组arr[i][j]，表示前i个物品中的若干个，放入体积为j的背包中的最大价值。

每次放入第i个物品，就更新这个数组

动态规划递推关系式：

if (j < vol[i]) //当前物品的体积比当前背包体积大，放不进背包
　　arr[i][j] = arr[i – 1][j];
else //放得进背包，逐一比较不放物品i与放物品i（背包体积为j-vol[j]）的价值大小
　　arr[i][j] = max(arr[i – 1][j], arr[i – 1][j – vol[i]] + cost[i]);

空间优化：arr[i][]只与arr[i-1][]有关，只需一个一维数组

 1 int main()
 2 {
 3     int cost[6] = { 0,2,5,3,10,4 };    //5件物品的价值
 4     int vol[6] = { 0,1,3,2,6,2 };    //5件物品的体积
 5     int bagV = 12;                    //背包体积
 6     while (cin >> bagV)
 7     {
 8         vector<vector<int>> arr(6, vector<int>(bagV + 1, 0));    //arr[6][bagV+1]数组初始化
 9         for (int i = 1;i < sizeof(cost) / sizeof(int);i++)
10         {
11             for (int j = 1;j <= bagV;j++)
12             {
13                 if (j < vol[i])        //当前物品的体积比当前背包体积大，放不进背包
14                     arr[i][j] = arr[i - 1][j];
15                 else        //放得进背包，逐一比较不放物品i与放物品i（背包体积为j-vol[j]）的价值大小
16                     arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - vol[i]] + cost[i]);
17                 cout << arr[i][j] << \'    \';
18             }
19             cout << endl;
20         }
21         cout << arr[5][bagV] << endl;
22     }
23     return 0;
24 }