By YiHeng

Updated:

Contents

​

01背包问题（每个物品最多只能放一次）
二维dp
初始化：dp[0][weight[0]]~dp[0][n-1]初始化为value[0],其他都为0。
以下两种都行:
1.先遍历物品，再遍历背包容量

1
2
3
4
5
6
7
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

2.先遍历背包容量，再遍历物品

1
2
3
4
5
6
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

一维dp只能先遍历物品，再遍历背包容量（这个必须倒叙遍历，否则物品会被重复放入计算）。
初始化：都为0即可（题目里数组都只包含正整数）。

1
2
3
4
5
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

完全背包（每个物品可以无限放，得到的结果是不分顺序的）
以下两种都行，完全背包的物品是可以添加多次的，所以要从小到大去遍历
1.先遍历物品，再遍历背包容量

1
2
3
4
5
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

2.先遍历背包容量，再遍历物品

1
2
3
4
5
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

  1. 零钱兑换 II中，需要得到凑出一定金额零钱的方式，需要求出的结果是组合数，所以只能用1。

    1.先遍历物品，再遍历背包容量，得到组合数。

    1
    2
    3
    4
    5
    6
    7
    518. for (int i = 0; i < coins.size(); i++) { // 遍历物品

        for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
            dp[j] += dp[j - coins[i]];
        }

    }

2.先遍历背包容量，再遍历物品，得到排列数。

1
2
3
4
5
for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}
Contents