0-1背包-动态规划

一、01背包

描述：有 N 件物品和一个容量为 V 的背包，每件物品只能使用一次

           第 i 件物品的体积是 Ci，价值是 Wi

           求解将哪些物品装入背包，能够在不超过背包容量的情况下使总价值最大

求解：动态规划

使用dp[i][j]表示从前 i 个物品中挑选，总体积不超过 j 的最大价值；则具有两种情况：

第一种情况：不选择第 i 个物品，那么此时的最大价值可以转化为：只放前 i - 1 件物品到容量为 j 的背包中的最大价值，故有：

                        ​​​​​​​        ​​​​​​​        ​​​​​​​        

第二种情况：选第 i 个物品，那么此时的最大价值可以转化为：将前 i - 1 件物品放到容量为j  - c[i]的背包中，加上此时得到的价值 Wi，故有:

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

最终结果取二者的较大值即可：

        ​​​​​​​        ​​​​​​​        

代码实现：

//N为物品数量, V为背包容量，c[i]为第 i 件物品的体积，w[i]为第 i 件物品的价值
public int knapsack(int N, int V, int[] c, int[] w){
    int[] [] dp = new int[N + 1][V + 1];
    //枚举物品
    for(int i = 1; i <= N; i++){
        //枚举体积
        for(int j = 1; j <= V; j++){
            //两种情况
            dp[i][j] = dp[i - 1][j];
            if(j >= c[i]){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
            }
        }
    }
    return dp[N][V];
}