动态规划:完全背包问题_java背包恰好装满问题

动态规划：完全背包问题

思路：转换成如下：

有一个背包，最大容量为amount,有一系列物品coins，每个物品重量为coins[i]，每个物品的重量无限，有多少种方法，能够把背包恰好装满

状态：

1.背包的容量

2.可选择的物品

选择：

装进背包/不装进背包

dp数组定义：若只使用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包。

    public static int change(int amount,int[] coins){
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        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];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

疑问：为什么j-coins[i-1]，这样不是相当于只用了一次coins[i-1]吗。