算法分析与设计：动态规划（空间复杂度优化）

背包问题

  由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有 X 元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱 X 以及 N 条哈士奇的价格和萌值，求高数巨最多可获得多少萌值。

Input

  多组输入。对于每组输入，第一行有两个整数 N,X(1 \leq N \leq 100，1 \leq X\leq1000)，分别表示哈士奇的数量和高数巨的钱数。接下来的 N 行每行有两个整数 P_i，M_i (1 \leq Pi,Mi \leq 100)，分别表示第 i 条哈士奇的价格和萌值。

Output

对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行。

Sample Input

2 100 50 20 60 40 3 100 20 55 20 35 90 95 1 10 20 50

Sample Output

40 95 0

实例代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, v;
    int w[1001], p[1001];
    while (~scanf("%d%d", &n, &v)) {
        for (int i = 0; i < n; i++) {
            // w 重量  | p 价值
            scanf("%d%d", &w[i], &p[i]);
        }
        // 重新初始化最优值结果数组
        int res[1001] = { 0 };
        for (int i = 0; i < n; i++) { // 存储的物品个数
            for (int k = v; k >= w[i]; k--) { // 从所需要的重量到当前重量
                res[k] = max(res[k], res[k - w[i]] + p[i]);
            }
        }
        printf("%d\n", res[v]);
    }
}

---

最少硬币问题

Problem Description

  设有 n 种不同面值的硬币，各硬币的面值存于数组 T[1:n] 中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins[1:n] 中。 对任意钱数 0 \leq m \leq 20001，设计一个用最少硬币找钱 m 的方法。 对于给定的 1 \leq n \leq 10，硬币面值数组 T 和可以使用的各种面值的硬币个数数组 Coins ，以及钱数 m ，0 \leq m \leq 20001 ，计算找钱 m 的最少硬币数。

Input

  输入数据第一行中只有 1 个整数给出 n 的值, 第 2 行起每行 2 个数，分别是 T[j] 和 Coins[j] 。最后 1 行是要找的钱数 m。

Output

  输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出 -1。

Sample Input

3 1 3 2 3 5 3 18

Sample Output

5

实例代码

#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int main()
{

    int m, n, T[20001], Coin[20001];
    int res[20001];
    memset(res, INF, sizeof(res));
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> T[i] >> Coin[i];
    }
    cin >> m;
    // res[目标面额] = 最小需求个数
    res[0] = 0;

    // 遍历面额值
    for (int i = 0; i < n; i++)
        // 遍历每种面额内有几张
        for (int j = 1; j <= Coin[i]; j++)
            // 遍历目标金额，选择当前这枚硬币是要还是不要
            for (int k = m; k >= T[i]; k--)
                // 将所有硬币依次拆分成单个，
                // res[目标面额] = min(res[目标面额 - 当前面额]+1，res[目标面额])，
                // 前一个是将该面额放入该组合中，后一个是不采用当前面额，选取数值最小的。
                res[k] = min(res[k - T[i]] + 1, res[k]);

    cout << (res[m] < INF ? res[m] : -1) << endl;
}

与“背包问题”的对比与分析

1. “背包”中给出了“损失”与“收益”，但其都是对于单个物品，求最大收益；“硬币”中给出的是“收益”、“个数”与“最终收益”，求最小组合。
2. 依旧采用一维数组 res[目标面额]= 最小需求个数 来存储最终结果。
3. 将所有硬币依次拆分成单个，res[目标面额] = min(res[目标面额 - 当前面额]+1，res[目标面额])，前一个是将该面额放入该组合中，后一个是不采用当前面额，选取数值最小的。

---

空间复杂度优化 （以背包问题为例）

  有很多人采用二维数组 res[i][j] 静态地更新来解决背包问题，使用二维数组更加直观，但是空间复杂度较高。

  如果采用一维数组动态更新看起来比较难理解，但使用范围比较广。(比如，最少硬币问题中，三重循环，也可以采用一维数组来解决，但如果使用二维的话，对应地应该上升到三维)。

难点：

“k:v->w[i]，依次递减”，这可能比较难以理解，在我们默认从小到大，而这里，必须从大到小，否则就是错误。

难点解答：

  产生上述问题，本质就是对 res[] 数组在某一时间其存储的值的不理解。

  对于每一次更新开始，res[]存储着的是“放入这个物品之前的最优解”，而我们比较的是 res[k] 与 res[k - w[i]] + p[i] (背包问题)，其中 res[k-w[i]]是之前的最优解。

  因为一定存在 k > k-w[i]，如果从小到大，则一定会先与 res[k] 更新 res[k-w[i]]，这就会导致比较错误。此时 res[k-w[i]] 已经变为“将该商品放入之后的最优价值”，在这价值基础之上，在加 p[i] ，其价值大概率会比 res[k] 高，而更新，这样，越来越大，完全背离了我们实际的意思。 因此，必须从后往前，因为前面存储着的是过去的值（不放第 i 件物品时的值）进行比较。

打赏