动态规划的解题步骤

  • 设计状态
  • 写出状态转移方程
  • 设定初始状态
  • 执行状态转移
  • 返回最终的解

动态规划和贪心的区别

  • 贪心：每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。
  • 动态规划：每一个状态一定是由上一个状态推导出来的。

01背包问题详解

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

状态转移方程

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

二维数组方法

vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));

for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = value[0];
}

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]);
    }
}

一维数组方法

vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
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]);
    }
}

为什么一维数组需要倒序，而二维数组不需要倒序？

  • 对于二维数组来说，上一次的状态是由dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
  • 而对于一维数组来说，如果正序遍历，会导致复用上一状态的结果，也就是状态会被累加

一维dp可不可以调换遍历顺序？

答案必须是不可以！如果调换顺序，会导致dp[j]只会被更新一次，因为dp[j]依赖的上一级状态并没有更新，这就导致了该背包只会被放入一个或者0个物品。

完全背包问题详解

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

状态转移方程

dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

二维数组方法

vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<vector<int>> dp(weight.size(), vector<int>(5, 0));

for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = max(value[0], value[0] + dp[0][j - weight[0]]);
}

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][j - weight[i]] + value[i]);
    }
}

一维数组方法

  • 先物品，后容量
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
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]);
    }
}
  • 先容量，后物品
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
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]);
        }
    }
}

二者区别

  • 如果是普通的纯完全背包，那么这两个for循环顺序没有影响
  • 如果需要计算组合或者排序数量那么就有影响
    • 如果求组合数就是外层for循环遍历物品，内层for遍历背包
    • 如果求排列数就是外层for遍历背包，内层for循环遍历物品
上次更新: