记录---完全背包问题（动态规划）_完全背包问题怎么记录选择情况

import java.util.Scanner;
/**
 * 有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
 * 可以看成完全背包问题
 * */
public class DP4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        String s = sc.nextLine();
        String[] s1 = s.split(" ");
        int[] arr = new int[s1.length];
        for (int i = 0; i <s1.length ; i++) {
            arr[i]=Integer.valueOf(s1[i]);
        }

        DP4 dp4 = new DP4();
        int res = dp4.dp(n, arr);
        System.out.println(res);
    }

    public int dp(int amount,int[] coins){
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        //base case 为dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
        for (int i = 0; i <n+1 ; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i <n+1 ; i++) {
            for (int j = 1; j <amount+1 ; j++) {
                if (j-coins[i-1]<0){
                    dp[i][j]=dp[i-1][j];
                }else{
                    //如果你不把这第i个物品装入背包，也就是说你不使用coins[i-1]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果。
                    //如果你把这第i个物品装入了背包，也就是说你使用coins[i-1]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]
                    // 当选择第i个物品时（与01背包问题相比，差别在i-1变成了i，因为01背包问题选了第i个，就不能选第二次，而这里可以重复选第i个）
                    //综上就是两种选择，而我们想求的dp[i][j]是「共有多少种凑法」，所以dp[i][j]的值应该是以上两种选择的结果之和
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44