背包问题

🚧🚧🚧 暂待施工🚧🚧🚧

01背包

public int maxValue(int[] weight, int[] value, int bagSize) {
    int goods = weight.length;
    int[][] dp = new int[goods + 1][bagSize + 1];
    
    for (int i = 1; i <= goods; i++) {
        for (int j = 1; j <= bagSize; j++) {
            if (j < weight[i - 1]) {
                dp[i][j] = dp[i - 1][j];
             } else {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i - 1][j - weight[i - 1]] + value[i - 1]
                    );
            }
		}
    }
    return dp[goods][bagSize];
    
}

滚动数组 压缩空间

public int maxValue(int[] weight, int[] value, int bagSize) {
    int goods = weight.length;
    int[] dp = new int[bagSize + 1];
    
    for (int i = 1; i <= goods; i++) {
        for (int j = bagSize; j >= 1; j--) {
            if (j >= weight[i - 1]) {
                dp[j] = Math.max(
                	dp[j],
                    dp[j - weight[i - 1]] + value[i - 1]
                );
            }
        }
    }
    
    return dp[bagSize];
}