动态规划（背包问题）--是否逆序使用的问题--二进制拆分的问题

题目链接

01背包

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
int n, V;
int v[1010], w[1010], dp[1010];
int main() {cin >> n >> V;for (int i = 0; i < n; i++)cin >> v[i] >> w[i];for (int i = 0; i < n; i++) {for (int j = V; j >= v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[V] << endl;return 0;
}

完全背包问题

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
int n, V;
int v[1010], w[1010], dp[1010];
int main() {cin >> n >> V;for (int i = 0; i < n; i++)cin >> v[i] >> w[i];for (int i = 0; i < n; i++) {//01背包这是逆序，以保证刚被放入的不会被放入第二次//完全背包没次数限制，只要保证局部最优解（像贪心）for (int j = v[i]; j <= V; j++) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[V] << endl;return 0;
}

多重背包问题 I

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
int n, V;
int v[1010], w[1010], s[1010], dp[1010];
int main() {cin >> n >> V;for (int i = 0; i < n; i++)cin >> v[i] >> w[i] >> s[i];for (int i = 0; i < n; i++) {//注意未放置重复使用，这里用的逆序for (int j = V; j >= 0; j--) {for (int k = 0; k <= s[i]; k++)if (j - v[i]*k >= 0)dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);}}cout << dp[V] << endl;return 0;
}

什么时候适用逆序

如果你的dp数组用的二维的话，就能确保状态更新时使用的是上一轮（即前一种物品）的值。

但是！ 可见我的代码dp数组全是用的一维数组，这个时候就有是否逆序的烦恼了呀！

那什么时候用逆序呢？

哎！先上总结：
原因如下：

首先，为什么要逆序遍历？防止重复选取：逆序保证在更新 dp[j] 时，dp[j - v[i]] 尚未被修改，即防止是上一轮的值被再次使用，哎~这就要有人问了，动态规划不就是递推的吗？不就是要用前几轮被更新的值吗？你想奥如果此时i=1，即仍然处于更新第一个物品的情况中，但是01背包中每个物品就一次，如果正序遍历，在内存允许的情况下，物品1又会被放一次。

但是什么情况下就无所谓呢？没错就是物品数量无限的时候，即完全背包问题。它没有数量限制，如果此时用逆序，就会导致在容量为V的时候只放了一共物品一，顺序的话就可以放V/v个物品一了。

那么多重背包为什么也要用逆序呢？多重背包多了一个参数——物品各自的数量，所以在双重循环中又加了一层，即数量的遍历，目的是遍历在数量允许的前提下时，容量允许的价值数量。
讲的比较抽象，轻喷：）

（虽然这个博客也没啥真人看（除了我自己）

多重背包问题 II（超百万级的复杂度）

百万级以内的复杂度，上述代码都能解决

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
//为什么是2w5？因为2000会被拆成11项，若2000个物品则一共就是2w2项
const int N = 25000;
int n, m, v[N], w[N], dp[N];
int main() {cin >> n >> m;int cnt = 0;
//实施二进制拆分for (int i = 1; i <= n; i++) {int a, b, s;cin >> a >> b >> s;int k = 1;while (k <= s) {cnt++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if (s > 0) {cnt++;v[cnt] = a * s;w[cnt] = b * s;}}for (int i = 1; i <= cnt; i++) {for (int j = m; j >= v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[m] << endl;return 0;
}

关于二进制拆分

这就有人要问了，和多重背包问题 I一模一样的题，还是一样的代码提交一遍不就好了嘛，水题！^ ^

对于多重背包问题 II，不一样的地方就是数据范围变大了，又是三重循环可想而知复杂度早就飙到不知道哪去了。

那么怎么解答呢？哎这就有大佬想到了，这个数字组合问题嘛，我们拆分就好了，怎么拆呢？哎~二进制拆分！！！（woc不知道谁想出来的，我第一次看震惊到我了，这么聪明的思路）

什么是二进制拆分呢？

假设你有7枚硬币，面值都是1元。现在想用这些硬币凑出0~7元中的任意金额。常规做法是带7枚硬币。
二进制拆分思路：
带1元、2元、4元的三枚硬币。你会发现这三枚硬币可以组合出0~7元的所有金额！！！（woc了nb）

这就是二进制拆分的核心思想：用最少的“虚拟物品”覆盖所有可能的数量组合。

处理次数对比一下

拆分完之后，再转换为01背包问题

哎~这么牛逼的算法想知道还能用在哪些地方吗？

哎！我就是这么的周到！

1、普通数据。例如：物品的件数、次数、文件大小（1000MB，拆分为 512MB, 256MB, 128MB, 64MB, 32MB, 8MB。）

2、快速幂算法：计算a^13 =a^1+ a^4+ a^8(对应1101) ，减少乘法次数

3、场景划分为不同大小的块（如 8x8, 16x16 像素）