题解 | #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;
    int[][] dp;
    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的背包中的最大容量
        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 j=vw[0][0];j<=V;j++)
        //     dp[0][j] = vw[0][1];
        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];




    }
    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]);

    }
}