【动态规划之完全背包问题】在实际问题中优化背包模型以及无效化情况的处理

⭐️前面的话⭐️

本篇文章将介绍动态规划中的背包问题——完全背包问题，前面我们已经介绍了什么是完全背包问题以及对应的解决方案以及练习，本文将列举一道实际问题来强化对完全背包的一维优化思维和无效化状态的处理。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年10月29日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

---

⭐️【一维优化强化以及无效状态】零钱兑换⭐️

🔐题目详情

322. 零钱兑换

难度中等

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

示例 2：

输入：coins = [2], amount = 3
输出：-1
1
2

示例 3：

输入：coins = [1], amount = 0
输出：0
1
2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

💡解题思路与代码

🍭朴素解法

首先我们来分析一下题目，题目给了我们很多硬币有各种面值，每种硬币可以选择无数次，需要求这些硬币和恰好为amount的最小所选硬币数。

这里我们可以将每一种硬币视为一种【物品】，amount可以视为背包的容量，硬币的面值可以看做物品的【体积】，所用的硬币数我们可以理解为【总价值】，则每种硬币的【价值】就是1，这样我们就能够将这个问题视作我完全背包问题。

状态定义： 不妨定义$f[i][j]$表示从前$i$种硬币中选择，恰好凑成$j$，所选物品的最小数量，由于硬币的面值是不定的，所以可能选择若干硬币可能凑不出amount，所以我们需要定义一个无效值来表示这个状态是无效的，也就是无法凑出amount的，由于我们求的是最小的硬币数，所以我们选择的无效值要比较大，可以选择Integer.MAX_VALUE。

确定初始状态： 当$i=0$时，只能选择第一个硬币，那么就尽量选，能凑成$j$，就加上所选的硬币个数，否则就将该状态赋值为无效值。

状态转移方程推导： 当我们选择第$i$种硬币的时候，我们可以选择$0,1,\mathrm{2...}k$枚，其中$k$是最大能够选择的硬币数，即在恰好凑出$j$的情况下。
假设第$i$件硬币的数值【体积】为$t$。
当我们不选择第$i$件硬币时，即$k=0$，$f[i][j]=f[i-1][j]$。
当我们选择$1$件第$i$件硬币时，即$k=1$，$f[i][j]=f[i-1][j-t]+1$。
当我们选择$2$件第$i$件硬币时，即$k=2$，$f[i][j]=f[i-1][j-2\ast t]+2$。
…
当我们选择$k$件第$i$件硬币时，即$k=k$，$f[i][j]=f[i-1][j-k\ast t]+k$。

我们所要求的是最小的硬币数量，所以取以上所有情况的最小值即可。

综上所述，我们的状态转移方程就出来了，当能够凑出$j$时，不妨记当前所选硬币的数量为：

$$f[i][j]=min(f[i-1][j-k\ast t]+k),k=0,1,...$$

但是选择$k$个硬币还是无法凑出`$j$时，该状态为无效值：

$$f[i][j]=INF$$

实现代码：

class Solution {
    //无效值
    private int INF = 0x3f3f3f;
    public int coinChange(int[] coins, int amount) {
        //获取硬币的个数
        int n = coins.length;

        int[][] f = new int[n][amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[0][j] = INF;
            else f[0][j] = k;
        }

        //状态转移
        for (int i = 1; i < n; i++) {
            int t = coins[i];
            for (int j = 0; j <= amount; j++) {
                //不选
                f[i][j] = f[i - 1][j];
                // 选k个
                for (int k = 1; j >= k * t; k++) {
                    if (f[i - 1][j - k * t] != INF) {
                        f[i][j] = Math.min(f[i][j], f[i - 1][j - k * t] + k);
                    }
                }
            }
        }
        return f[n - 1][amount] == INF ? -1 : f[n - 1][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

时间复杂度：$O(amoun{t}^2\ast n)$，$k$的值不会大于$amount$，因为$t$最小为$1$，最多选择的数的数量不会超过$amount$。
空间复杂度：$O(n\ast amount)$

🍭滚动数组优化空间

根据观察我们知道第$i$行的状态仅依赖与第$i-1$行的状态，因此我们可以使用滚动数组进行优化。

实现代码：

class Solution {
    //无效值
    private int INF = 0x3f3f3f;
    public int coinChange(int[] coins, int amount) {
        //
        int n = coins.length;

        int[][] f = new int[2][amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[0][j] = INF;
            else f[0][j] = k;
        }

        //状态转移
        for (int i = 1; i < n; i++) {
            int t = coins[i];
            int pre = (i - 1) & 1;
            int cur = i & 1;
            for (int j = 0; j <= amount; j++) {
                //不选
                f[cur][j] = f[pre][j];
                // 选k个
                for (int k = 1; j >= k * t; k++) {
                    if (f[pre][j - k * t] != INF) {
                        f[cur][j] = Math.min(f[cur][j], f[pre][j - k * t] + k);
                    }
                }
            }
        }
        return f[(n - 1) & 1][amount] == INF ? -1 : f[(n - 1) & 1][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

对于时空复杂度，只是优化了空间而已，所以时间复杂度不发生改变，空间复杂度优化到$O(amount)$。
时间复杂度：$O(amoun{t}^2\ast n)$，$k$的值不会大于$amount$，因为$t$最小为$1$，最多选择的数的数量不会超过$amount$。
空间复杂度：$O(amount)$

🍭一维数组优化空间

首先我们对状态转移方程进行一个简单的推导：

$$f[i][j]=min(f[i-1][j],f[i-1][j-t]+1,f[i-1][j-2\ast t]+2,...,f[i-1][j-kt]+k)$$

$$f[i][j-t]=min(f[i-1][j-t],f[i-1][j-2t]+1,f[i-1][j-3t]+\mathrm{2...},f[i-1][j-kt]+k-1)$$

其中$k\ast t<=j$。

通过观察上面两个状态的式子，我们发现后面一部分式子是差了一个$1$如下图：

所以我们可以进一步优化状态转移方程，即：

$$f[i][j]=min(f[i-1][j],f[i][j-t]+1)$$

对于新推导出来的状态转移方程，它的状态转移仅仅只依赖与上一行同列状态与同一行元素前面的元素，所以我们可以将原来的二维数组优化为一维，由于它只依赖左边与正上方的元素，我们可以采取从小到大遍历背包容量状态来求背包中所放物品最大值。

只保留【凑出amount】维度，状态转移方程为：

$$f[j]=max(f[j],f[j-t]+1)$$

前面我们定义了一个INF，取值为整型的最大值，其实我们可以预留一些空间，就是取一个比最大值小一点的数，这样在就给了这个无效值累加的空间，不会出现越界变为负数的问题，这样我们就可以不用在进行判断前一个依赖的状态是否是INF。

实现代码：

class Solution {
    private static final int INF = 0x3f3f3f3f;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;

        int[] f = new int[amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[j] = INF;
            else f[j] = k;
        }

        for (int i = 0; i < n; i++) {
            int t = coins[i];
            for (int j = t; j <= amount; j++) {
                f[j] = Math.min(f[j], f[j - t] + 1);
            }
        }
        return f[amount] == INF ? -1 : f[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：$O(amount\ast n)$
空间复杂度：$O(amount+1)$

🌱总结

本篇文章介绍了【完全背包】的运用，使用该模型运用到实际的问题当中，强化一维优化过程的推导。

对于完全背包的优化，相比于0-1背包问题的优化，形式上，我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子：
0 -1 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。

---

参考资料： 宫水三叶背包问题

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！