思路：

维持一个数组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
     
      
       > arr(6, vector
       
        (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 }