2022-06-11

有n件物品和一个容量为v的背包。放入第i件物品的占的空间为Ci,得到的价值是Wi,求解将哪些物品装入背包可以

     使得总价值最大；

    首先要明白这个问题不能用贪心来做，因为当前的选择会影响到以后的选择，也就是说当前的选择的最优解

    可能会影响到全局的最优解；

   考虑用动态规划来做

       1.定义状态：

                定义状态dp[i][j]为前i件物品恰放入容量为j的背包时的最大价值；

                那么dp[n][v]就是这个问题的最终解；

       2.描述不同状态如何转移： 

                 在这个过程中，我们很自然想到的决策就是第i件物品放还是不放；放与不放会直接影响到dp[i][j]的值；

                1.放，那么dp[i][j]的状态可由dp[i-1][j-Ci] + Wi转移过来

                2.不放，那么dp[i][j]的状态可由dp[i-1][j]转移过来

                我们所要做的就是在这两种决策中选取一种最优的；

                  所以状态转移方程为dp[i][j] = max(dp[i-1][j-Ci] + Wi , dp[i-1][j]);