目录

• 一：0-1背包
• 完全背包

一：0-1背包

描述：给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i] ，价值为 val[i] ，现在让你⽤这个背包装物品，最多能装的价值是多少？

dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w ，这种
情况下可以装的最⼤价值是 dp[i][w] 。

//0-1背包
//给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两
//个属性。其中第 i 个物品的重量为 wt[i] ，价值为 val[i] ，现在让你⽤
//这个背包装物品，最多能装的价值是多少？
//输出为最多能装的价值

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();
        int[] wt = new int[N];
        int[] val = new int[N];
        for(int i = 0; i < N; i++){
            wt[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }
        System.out.println(knapstack(N, W, wt, val));
    }

    private static int knapstack(int N, int W, int[] wt, int[] val){
        int[][] dp = new int[N + 1][W + 1];
        //base case
        for(int i = 0; i <= N; i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= W; j++){
            dp[0][j] = 0;
        }

        for(int i = 1; i <= N; i++){
            for(int w= 1; w <= W; w++){
                if(w - wt[i - 1] < 0){
                	// 这种情况下只能选择不装⼊背包
                    dp[i][w] = dp[i - 1][w];
                }else{
                	// 装⼊或者不装⼊背包，择优
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
                }
            }
        }
        return dp[N][W];
    }

    private static int maxValue(int N, int W, int[] wt, int[] val){
        if(N == 0 || W == 0){
            return 0;
        }
        int[] dp  = new int[W + 1];
        for(int i = 0; i < N; i++){
            for(int j = W; j >= wt[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - wt[i]] + val[i]);
            }
        }
        return dp[W];
    }


}

完全背包

有⼀个背包，最⼤容量为 amount ，有⼀系列物品 coins ，每个物品的重
量为 coins[i] ，每个物品的数量⽆限。请问有多少种⽅法，能够把背包恰
好装满？

dp[i][j] 的定义如下：
若只使⽤前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种⽅法可以装
满背包。

base case 为 dp[0][…] = 0， dp[…][0] = 1 。

int change(int amount, int[] coins) {
	int n = coins.length;
	int[][] dp = amount int[n + 1][amount + 1];
	// base case
	for (int i = 0; i <= n; i++)
		dp[i][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= amount; j++)
			if (j - coins[i-1] >= 0)
				dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]];
			else
				dp[i][j] = dp[i - 1][j];
	}
	return dp[n][amount];
}