题解 | #01背包#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int maxValue = 0;
   
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        //方法一暴力解法：回溯法
        // dfs(V,n,vw,0,0,0);
        // return maxValue;


        //方法二：动态规划二维数组dp
        //dp的序号i,j表示任取0-i的物品存放在容量为j的背包中的最大容量
        // int[][] dp;
        //dp = new int[n + 1][V + 1];
        //首先初始化dp,第一列全为0，表示将前i个物品存放在容积为0的背包
        //第一行中容积为vw[0][0]以及之后的背包重量为vw[0][1]，之前背包重量为0
        //其余dp只需依据它的上一行的正上方或左上角就可以得出
        // Arrays.fill(dp[0], 0);
        // for (int i = 1; i <= n; i++)
        //     dp[i][0] = 0;
        // for (int i = 1; i <= n; i++)
        //     for (int j = 0; j <= V; j++) {
        //         //dp[i][j]分为两种情况，一种是第i个物品存放在背包中，另一种是第i个物品没有存放在背包中
        //         if (j < vw[i - 1][0]) {
        //             dp[i][j] = dp[i - 1][j];
        //         } else {
        //             dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
        //         }
        //         //dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);

        //     }
        // return dp[n][V];


        //方法三：动态规划优化，滚动数组，将dp由二维降到一维
        //由于计算dp[i][j]需要借助上一行的dp值，可以通过将上一行的dp值复制到当前数组中，这样就转为了一维数组，然后倒序访问数组计算，如果顺序计算会影响到之后的dp计算
        int[] dp=new int[V+1];
        Arrays.fill(dp,0);
        for(int i=1;i<=n;i++)
            for(int j=V;j>=vw[i-1][0];j--){
               
                dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
                
            }
        return dp[V];


    }
    public void dfs(int V, int n, int[][] vw, int index, int sumV, int sumW) {
        if (index == n) {
            return;
        }
        dfs(V, n, vw, index + 1, sumV, sumW);
        if (sumV + vw[index][0] <= V) {
            maxValue = maxValue < sumW + vw[index][1] ? sumW + vw[index][1] : maxValue;
        }
        dfs(V, n, vw, index + 1, sumV + vw[index][0], sumW + vw[index][1]);

    }
}