题目链接
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 像素）