前言：
古有陈天华万字血书抗沙俄，今有本剧蒻万字背包虐dp
本文介绍了01背包、完全背包、多重背包、混合背包、分组背包等背包，并对其进行透彻的剖析，并附上了板子题，供您白嫖，以及一些奇葩变式，颇有意思，供你琢磨玩弄。此外绝大部分题都有二维数组和滚动数组的解析及代码，包您满意（那我们现在就让数组滚动起来叭o(≧v≦)o）
背包入门之01背包
简化的01背包
题意：
有一个箱子容量为V，同时有n个物品，每个物品有一个体积，要求n个物品中取若干个装进箱子，使得箱子的剩余空间最小
思路：
贪心是绝对不可以滴，怎么贪都不行滴
动态规划的话得找好状态，这个题是不可以选剩余空间为状态的，因为会有历史遗留问题，就是对于一个新来的物品，可能可以替换之前出现的物品而使得剩余体积更小，历史遗留问题没有得到解决
所以换个状态：dp[i] [j]表示前i个物品，能否恰好装满体积为j的背包
对于第i个物品，有两种选择，可以选也可以不选，对与j的体积，可能不选第i个物品，体积为j的背包就已经满了，也可能是选第i个物品，且体积为j的背包剩余体积为v-tr[i]，这样就恰好选第i个物品导致背包装满
状态转移方程：dp[i] [j] = dp[i – 1] [j] || dp[i – 1] [j – tr[i]]
#inlcude<bits/stdc++.h>
using namespace std;
int v, n, x;
int dp[100][100], tr[100];
int main(){
cin>>v>>n;
for(int i = 1; i <= n; ++i)tr[i] = IntRead();
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){//行为前i个物品
for(int j = 0; j <= v; ++j){//列为j的体积，从0开始！
if(j >= tr[i])dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - tr[i]]);
//看看当前的体积j是否大于第i个物品的体积，如果小于就会发生数组越界，
else dp[i][j] = dp[i - 1][j];
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= v; ++j){
cout<<dp[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
/*
24 6
8 3 12 7 9 7
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0
0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
*/
上述方法的时间复杂度是O(N * V),，而空间复杂度就比较高，得开
N * V大小的二维数组，遇到一些毒瘤数据直接能卡爆你
我们观察上述样例的结果，会发现每一行都会承接上一行的数，并继续算后面的数，所以，我们就可以进行优化，滚动数组（其实我喜欢这样称呼他：让数组滚动起来o(≧v≦)o）
虽然空间复杂度降了很多，但是时间复杂度是没有变的（世界上哪有十全十美的事情(⌒▽⌒)），还是进行双层for循环，第一层是循环物品，第二层是循环体积
我们直接让数组从前往后滚动起来其实是有问题的，
本来的状态方程是dp[i] [j] = dp[i – 1] [j] || dp[i – 1] [j – tr[i]]
但不用二维数组后，就相当于直接把他变成：dp[j] = dp[j – tr[i]] || dp[j] ,这是不对的，本来是在上一行的数基础上进行更新，现在变成同一行，就相当于把状态方程变成了dp[i] [j] = dp[i] [j] || d[i] [j – tr[i]]
你将自己的dp[i] [j]也算进去了，就会导致在这一维数组中，你会将满足dp[j] = d[j – tr[i]] 的都算进去了，这样就不对，因为你的物品的个数只有一个，而你现在相当于是无限个
所以我们进行一下修改，对于第二层循环，我们从后往前进行循环，这样就能避免上述情况
#inlcude<bits/stdc++.h>
using namespace std;
int v, n, x;
int dp[100], tr[100];
int main(){
cin>>v>>n;
for(int i = 1; i <= n; ++i)tr[i] = IntRead();
dp[0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = v; j >= tr[i]; --j){
if(dp[j - tr[i]])dp[j] = 1;
//这里就不需要考虑越不越界的问题了，因为j最小就是tr[i]
}
for(int i = 1; i <= v; ++i)cout<<dp[i]<<' ';
return 0;
}
/*
24 6
8 3 12 7 9 7
*/
对于本题，我们需要的是最最后一行从后往前遍历，找到第一个1的位置去输出答案
01背包
题意：
有n件物品和一个容量为v的背包，第i件物品的费用是c[i]，价值是w[i]，求解哪些物品装入背包可使总价值和最大
思路：
dp
确定状态：dp[i] [j]表示对于前i个物品，体积为j的背包能获得的最大价值是多少
状态转移方程：dp[i] [j] = max(dp[i – 1] [j], dp[i – 1] [j – c[i] + w[i])
对于初始状态的赋值有两种，一种是只对dp[0] [0] = 0,这样最后就需要对最后一行进行遍历找答案；另一种是对dp[0] [j]全赋0，这样最后一个数就是我们需要的最大价值
#inlcude<bits/stdc++.h>
using namespace std;
int t, n, x;
int dp[100][100], c[100], w[100];
void init(){//赋值方法一
memset(dp, -inf, sizeof(dp));
dp[0][0] = 0;
}
int main(){
cin>>t>>n;
for(int i = 1; i <= n; ++i){cin>>c[i]>>w[i];}
init();
for(int i = 1; i <= n; ++i)for(int j = 0; j <= t;++j){
if(j >= c[i])//特判，防止数组越界
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - c[i]] + w[i]);
else dp[i][j] = dp[i - 1][j];
}
for(int i = 0; i <= n; ++i){
cout<<i<<' ';
for(int j = 0; j <= t; ++j){
if(dp[i][j] >= 0)cout<<dp[i][j]<<' ';
else cout<<"X ";
}
cout<<endl;
}
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
0 0 X X X X X X X X X X X X
1 0 X X X X 10 X X X X X X X
2 0 X X 7 X 10 X X 17 X X X X
3 0 X 4 7 X 11 X 14 17 X 21 X X
4 0 X 4 7 3 11 7 14 17 14 21 17 20
5 0 X 4 7 3 17 7 21 24 20 28 24 31
6 0 X 4 7 8 17 12 21 24 25 28 29 32
*/
另一种赋值法：
#inlcude<bits/stdc++.h>
using namespace std;
int t, n, x;
int dp[100][100], c[100], w[100];
void init(){//赋值方法二，对第1行的值赋0
memset(dp, -inf, sizeof(dp));
for(int i = 0; i <= t; ++i)dp[0][i] = 0;
}
int main(){
cin>>t>>n;
for(int i = 1; i <= n; ++i){cin>>c[i]>>w[i];}
init();
for(int i = 1; i <= n; ++i)for(int j = 0; j <= t;++j){
if(j >= c[i])//特判，放越界
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - c[i]] + w[i]);
else dp[i][j] = dp[i - 1][j];
}
for(int i = 0; i <= n; ++i){
cout<<i<<' ';
for(int j = 0; j <= t; ++j){
if(dp[i][j] >= 0)cout<<dp[i][j]<<' ';
else cout<<"X ";
}
cout<<endl;
}
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 10 10 10 10 10 10 10 10
2 0 0 0 7 7 10 10 10 17 17 17 17 17
3 0 0 4 7 7 11 11 14 17 17 21 21 21
4 0 0 4 7 7 11 11 14 17 17 21 21 21
5 0 0 4 7 7 17 17 21 24 24 28 28 31
6 0 0 4 7 8 17 17 21 24 25 28 29 32
*/
//观察一下这个输出的结果和上面的输出结果，就会发现，这个的最大值就在右下角，就省去了最后去循环的过程
同样的，我们可以让数组滚动起来！o(≧v≦)o
最后还需要对数组遍历一遍得到答案
#inlcude<bits/stdc++.h>
using namespace std;
int t, x, n;
int c[100], w[100], dp[100];
int main(){
cin>>t>>n;
for(int i = 1; i <= n; ++i)cin>>c[i]>>w[i];
dp[0] = 0;//初始化
for(int i = 1; i <= n; ++i)for(int j = t; j >= c[i]; j--){
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
for(int i = 0; i <= t; ++i)cout<<dp[i]<<' ';
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
0 0 4 7 8 17 17 21 24 25 28 29 32
*/
01背包之变态数据
N <= 20, V <= 10 ^ 9
背包体积太大怎么办？？？
对于上面的做法空间开不了，时间也耗不起，那怎么办？
我们观察一下数据n是小于20，对于20个物品，我们可以直接暴力枚举每个物品选还是不选，2^20 大约为1e6，时间过得去，空间也过得去，所以就进行01串模拟
从1到（（1<<n） – 1）进行暴力，每一位，如果是1就选，是0就不选
用set来存一下最大价值，最好输出最大的那个即可
#inlcude<bits/stdc++.h>
using namespace std;
int v, x, n, sum, k, j, cnt, len;
int c[100], w[100], dp[100];
set<int>se;
int main(){
cin>>v>>n;
for(int i = 1; i <= n; ++i)cin>>c[i]>>w[i];
k = (1 << n) - 1;
for(int i = 1; i <= k; ++i){
sum = 0;x = i;j = 1;cnt = 0;
while (x) {
if((x & 1) == 1){
sum += w[j];
cnt += c[j];
}
++j;x >>= 1;
}
if(cnt <= v)se.insert(sum);
}
set<int>::iterator it;
for(it = se.begin(); it != se.end(); ++it)cout<<*it<<' ';
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
3 4 7 8 10 11 12 13 14 15 17 18 19 20 21 22 24 25 27 28 29 31 32
*/
N <= 40, V <= 109
n比上次的翻了一倍，这样就没办法之间打打暴力了，因为2^40 大约是1e12，会超时
但是我们观察一下会发现，40是20的2倍，所以我们可以将这40个物品拆成2部分，分别打暴力，然后进行合并
打暴力还是用01串去枚举，对于每次枚举完了就用map存体积和价值，两次暴力打完了以后，就对其中一个map进行迭代，假如这次迭代的体积是vv，价值是ww，那说明v的体积下还可以塞进v-vv的体积，所以我们对剩下的那个map去lowerbound （v – vv）的值，然后将其价值和ww加起来塞进set中，最后输出set的最后一个元素即可
#inlcude<bits/stdc++.h>
using namespace std;
int v, n, x, k, sum, cnt, j, aa;
int c[100], w[100];
set<int>se;
map<int, int>mp1;
map<int, int>mp2;
int main(){
cin >> v >> n;
for(int i = 1; i <= n; ++i)cin>>c[i]>>w[i];
k = (1 << n / 2) - 1;//分两份
for(int i = 1; i <= k; ++i){
x = i;sum = 0;cnt = 0;j = 1;
while (x) {
if((x & 1) == 1){
cnt += c[j]; sum += w[j];
}
x >>= 1;++j;
}
//符合条件的就塞进map
if(cnt <= v)mp1[cnt] = max(mp1[cnt], sum);
}
for(int i = 1; i <= k; ++i){//重复上述操作，不够范围得改
x = i;sum = 0;cnt = 0;j = n / 2 + 1;
while (x) {
if((x & 1) == 1){
cnt += c[j]; sum += w[j];
}
x >>= 1;++j;
}
if(cnt <= v)mp2[cnt] = sum;
}
map<int, int>::iterator it;//用来迭代mp1
map<int, int>::iterator itt;//用来接受lowerbound的值
set<int>::iterator ittt;//迭代set
for(it = mp1.begin(); it != mp1.end(); ++it){
aa = v - it->first;
itt = mp2.lower_bound(aa);
se.insert(it->second + itt ->second);
}
for(ittt = se.begin(); ittt != se.end(); ++ittt)cout<<*ittt<<' ';
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
0 0 4 7 8 17 17 21 24 25 28 29 32
*/
N <= 100 V <= 1e9
一看到数据，第一反应是不是这他喵玩个屁？？
确实，这确实没办法向上面那样暴力了o(︶︿︶)o
但是我们还有方法！
先拿出第一次写二维dp的样例图
0 X X X X X X X X X X X X
0 X X X X 10 X X X X X X X
0 X X 7 X 10 X X 17 X X X X
0 X 4 7 X 11 X 14 17 X 21 X X
0 X 4 7 3 11 7 14 17 14 21 17 20
0 X 4 7 3 17 7 21 24 20 28 24 31
0 X 4 7 8 17 12 21 24 25 28 29 32
对于第一行，有用的只有0
对于第二行有用的只有0和10
剩下的同理
就是因为有辣么多没有用到的数才导致数组很大，所以我们就用map存一下有用的数，然后进行dp即可
同时还有进行优化：
比如第五行，从后往前计算的时候，发现3比他前面的7小，说明插3没有用，占的地方大，价值还小，所以直接删掉，就是说得让数据是递增的（虽然这个地方我才疏学浅，实现不了，只能说是勉强实现一内内）
#inlcude<bits/stdc++.h>
using namespace std;
int v, n, x, k, sum, cnt, j, aa;
int c[100], w[100];
map<int, int>mp1;
int main(){
cin >> v >> n;
for(int i = 1; i <= n; ++i)cin>>c[i]>>w[i];
mp1[0] = 0;//赋初值,最后记得删
mp1[c[1]] = w[0];//将第一个数扔进去
map<int, int>::reverse_iterator it;//从后往前遍历
for(int i = 2; i <= n; ++i){
//正常的进行dp，
for(it = mp1.rbegin(); it != mp1.rend(); ++it){
mp1[it -> first + c[i]] = max(mp1[it -> first + c[i]], it -> second + w[i]);
//这里我词穷了，你看着办吧
if(mp1[it -> first + c[i]] < it ->second)
mp1.erase(mp1[it -> first + c[i]]);
//这里本来应该是比较要插入的元素和要插入的位置的前一个的大小，但是我不知道怎么获得前一个位置的值，因为我有的只是我需要插入的点first的值，并不知道他的迭代器应该在哪里(╥﹏╥)
}
}
mp1.erase(0);//删了0，其实不删也没事
map<int, int>::iterator itt;
for(itt = mp1.begin(); itt != mp1.end(); ++itt){
if(itt ->first <= v)
cout<<itt->first<<' '<<itt->second<<endl;
}
return 0;
}
/*
12 6
5 10
3 7
2 4
4 3
5 17
4 8
2 4
3 7
4 8
5 17
6 12
7 21
8 24
9 25
10 28
11 29
12 32
*/
温馨提示：
我上述写的有些代码并未经oj提交，只是听了雨巨口描述的题干后写的代码，可能会出问题，不过我感觉这种变式题考的可能性比较低，了解了解思路就可以啦
01背包例题及变式
P1048 [NOIP2005 普及组] 采药
题意：
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
思路：
01背包板子题哈，直接让数组滚动起来趴
#inlcude<bits/stdc++.h>
using namespace std;
int t, m;
int c[MAX], w[MAX], dp[MAX];
int main(){
cin>>t>>m;
for(int i = 1; i <= m; ++i){
cin>>c[i]>>w[i];
}
dp[0] = 0;
for(int i = 1; i <= m; ++i)
for(int j = t; j >= c[i]; --j){
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
// for(int i = 1; i <= t; ++i)cout<<dp[i]<<' ';
cout<<dp[t]<<endl;
return 0;
}
P1060 [NOIP2006 普及组] 开心的金明
题目描述：
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的NN元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-51−5表示，第55等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过NN元（可以等于NN元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
请你帮助金明设计一个满足要求的购物单。
题意：
我有n元钱，有m个物品想买，给出每个物品的价格和重要度，在不超过n元的基础上，使得选出来的物品的价格和重要度最大
思路：
还是01背包，没什么大的变化，只是这次的价值变成了价格 * 重要度
#inlcude<bits/stdc++.h>
using namespace std;
int n, m, x;
int dp[MAX], v[MAX], w[MAX];
int main(){
cin>>n>>m;
for(int i = 1; i <= m; ++i){
cin>>v[i]>>x;
w[i] = v[i] * x;
}
for(int i = 1; i <= m; ++i){
for(int j = n; j >= v[i]; --j){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout<<dp[n]<<endl;
}
P1049 [NOIP2001 普及组] 装箱问题
题意：
一个体积为V的背包，对于n个物品，问你箱子的最小剩余体积为多少
思路：
这就是我最开始讲的那个简化版的01背包
确定状态：
dp[i] [j] 表示前i个物品，能否完全装满 j 的体积
状态转移方程：
二维：dp[i] [j] = (dp[i – 1] [j] || dp[i – 1] [j – tr[i]])
一维：dp[j] = dp[j] || dp[j – tr[i]]
#inlcude<bits/stdc++.h>
using namespace std;
int v, n, x;
int dp[MAX], tr[MAX];
int main(){
cin>>v>>n;
for(int i = 1; i <= n; ++i)cin>>tr[i];
dp[0] = 1;
for(int i = 1; i <= n; ++i){
for(int j = v; j >= tr[i]; --j){
dp[j] = (dp[j] || dp[j - tr[i]]);
}
}
int sum = 0;//计算剩余的体积
for(int i = v; i >= 0; --i){//从后往前遍历，去找到第一个塞满的位置，然后输出
if(dp[i] == 1){
cout<<sum<<endl;
break;
}
sum++;
}
return 0;
}
P1164 小A点菜
题意：
M元，N种菜，问将钱花光的方法有多少种
思路：
这个题可以dfs，但是我没试，不知道会不会超时
还可以用dp来做
确定状态
dp[i] [j] 表示前i个物品，花光 j 元的方法数
分析状态转移
对于背包问题都是靠虑该物品选还是不选
所以第一种可能是不选该物品就已经花光了 j 元，也就是这样的
对于第二种可能是选该物品，此时正好花完 j 元，也就是这样的
但有种特殊情况，就是 j = tr[i] 的时候，加的是tr[i – 1] [0]，在没有赋初值的情况下就是0，相当于没有加，但其实应该加1，所以可以特判一下也可以赋初值为1，我这里是特判的o(≧v≦)o
状态转移方程：
#inlcude<bits/stdc++.h>
using namespace std;
int n, m, x;
int dp[105][10005], tr[MAX];
int main(){
cin>>n>>m;
for(int i = 1; i <= n; ++i)cin>>tr[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
dp[i][j] += dp[i - 1][j];
if(j > tr[i])dp[i][j] += dp[i - 1][j - tr[i]];
else if(j == tr[i])dp[i][j] += 1;
}
cout<<dp[n][m]<<endl;
return 0;
}
二维解决了以后就到了让数组滚动起来的时候，根据之前讲的，二维降一维少的是行，也就是变成了
因为滚动起来的循环是从m到tr[i]，所以不存在 j < tr[i]的情况，再加上我们给dp[0] = 1，就可以避免j = tr[i]的问题的出现，最后状态转移方程就可以简化成上述公式，是不是很简洁orz
#inlcude<bits/stdc++.h>
using namespace std;
int n, m, x;
int dp[MAX], tr[MAX];
int main(){
cin>>n>>m;
for(int i = 1; i <= n; ++i)cin>>tr[i];
dp[0] = 1;//赋初值
for(int i = 1; i <= n; ++i)
for(int j = m; j >= tr[i]; --j){//滚动数组注意变量范围
dp[j] += dp[j - tr[i]];
}
cout<<dp[m]<<endl;
return 0;
}
P1510 精卫填海
题目描述：
东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。
思路：
01背包问题，不过得选好变量去循环
对于这个题是挑选的物品的体积和至少大于等于 v 才可以，在此基础上去找剩余最大的体力，如果像之前的背包一样去循环体积的话，你就根本没法找，可能你选的物品的体积大于v，且用的体力还很少，就没法了。
所以我们换一种状态：
最后对于1到c的体力去从前遍历，遇到第一个大于 v 的就输出\
状态转移方程
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f2
#define MAX 100000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef long long ll ;
using namespace std;
int gcd(int a, int b){if(b) return gcd(b, a % b);else return a;}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int v, n, c, ans;
int k[MAX], m[MAX], dp[10005];
int main(){
cin>>v>>n>>c;
for(int i = 1; i <= n; ++i)cin>>k[i]>>m[i];
for(int i = 1; i <= n; ++i)
for(int j = c; j >= m[i]; --j){
dp[j] = max(dp[j], dp[j - m[i]] + k[i]);
}
ans = -1;
for(int i = 1; i <= c; ++i){
if(dp[i]>= v){
ans = c - i;
break;
}
}
if(ans == -1)cout<<"Impossible\n";
else cout<<ans<<endl;
}
P1734 最大约数和
题意：
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
思路：
简单的01背包问题，不过得注意什么是“体积”，什么是“价值”
s是背包的总体积，物品最多1000个，每个物品的体积就是i，价值是i的所有约数和（不包括自己本身），然后打个dp就可以
#inlcude<bits/stdc++.h>
using namespace std;
int dp[MAX], c[MAX], w[MAX];
int s;
int f(int x){
int sum = 0;
for(int i = 1; i < x; ++i){
if(x % i == 0)sum += i;
}
return sum;
}
int main(){
cin>>s;
for(int i = 1; i <= 1000; ++i){
c[i] = i;w[i] = f(i);
}
for(int i = 1; i <= s; ++i){
for(int j = s; j >= c[i]; --j){
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
}
cout<<dp[s]<<endl;
return 0;
}
P1466 [USACO2.2]集合 Subset Sums
题意：
对于前n个数，划分成两个子集和，使得这两个子集和的数字和是相同的，交换集合位置被认为是一种划分方式
思路：
01背包
背包体积是（n + 1）* n / 4，找到能使得背包完全装满的方案数
状态：
状态转移方程：
注意初试值
#inlcude<bits/stdc++.h>
using namespace std;
int n, k;
ll dp[1005];
int main(){
cin>>n;
if((n + 1) * n % 4 != 0)cout<<0<<endl;
else{
k = (n + 1) * n / 4;
dp[0] = 1;
//cout<<k<<endl;
for(int i = 1; i <= n; ++i)
for(int j = k; j >= i; --j){
dp[j] += dp[j - i];
}
cout<<dp[k] / 2<<endl;
}
return 0;
}
背包进阶之完全背包
完全背包就是在01背包的基础上，每个物品可以取无数次，问你能获得的最大的价值是多少
确定状态：
dp[i] [j]依然表示前i个物品放入体积为j的背包所能获得最大价值
状态转移方程：
dp[i] [j] = max(dp[i – 1] [j – k * c[i]] + k * w[i])，其中（0 <= k * c[i] <= j)
时间复杂度：
这复杂度出题人脑子但凡没有问题都会卡你，不过总有例外(>_<)
#inlcude<bits/stdc++.h>
using namespace std;
int t, m;
int ar[10000], br[10000];
ll dp[MAX];
int main(){
t = IntRead(); m = IntRead();
for(int i = 1; i <= m; ++i){ar[i] = IntRead();br[i] = IntRead();}
dp[0] = 0;
for(int i = 1; i <= m; ++i)
for(int j = ar[i]; j <= t; ++j){
dp[j] = max(dp[j], dp[j - ar[i]] + br[i]);
}
cout<<dp[t]<<endl;
//for(int i = 1; i <= t; ++i)cout<<dp[i]<<' ';
return 0;
}
/*
70 3
71 100
69 1
1 2
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140
*/
P1679 神奇的四次方数
题意：
将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=54+34,则n=2。
思路：
这个题每个数可以取的数量不限，所以是一个多重背包
整数m相当于背包的体积v，看题目数据范围是1e5，所以掏出我们的计算器算一下，18的四次方就超过了1e5，所以物品有17个，每个物品的体积就是i^4，求的是选的最少的物品数量
状态：
状态转移方程：
#inlcude<bits/stdc++.h>
using namespace std;
int n;
int dp[MAX], w[25];//w代表价值
int main(){
for(int i = 1; i <= 20; ++i){
c[i] = i;w[i] = pow(i, 4);
}
memset(dp, inf, sizeof(dp));//要给dp赋无穷大
dp[0] = 0;//把第一个位置初始化为0
cin>>n;
for(int i = 1; i <= 18; ++i){
for(int j = w[i]; j <= n; ++j){
dp[j] = min(dp[j], dp[j - w[i]] + 1);
}
}
cout<<dp[n]<<endl;
return 0;
}
多重背包
多重背包是在01背包的基础上规定了每个物品可以选取的件数
很显然其状态转移方程是
注意这里不只是选与不选了，而是选几个，所以不要写成dp[i – 1] [j]了，并且k是从0开始选的！
#inlcude<bits/stdc++.h>
using namespace std;
int n, v;
struct ran{
int c, w, s;
}tr[MAX];
ll dp[105][105];
int main(){
cin>>n>>v;
for(int i = 1; i <= n; ++i){
tr[i].c = IntRead();tr[i].w = IntRead();tr[i].s = IntRead();
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= v; ++j){
for(int k = 0; k <= tr[i].s; ++k){
if(j >= k * tr[i].c)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * tr[i].c] + tr[i].w * k);
}
}
}
cout<<dp[n][v]<<endl;
return 0;
}
二维是这样滴，现在让数组滚动起来趴！
#inlcude<bits/stdc++.h>
using namespace std;
int n, v;
struct ran{
int c, w, s;
}tr[MAX];
int dp[MAX];
int main(){
cin>>n>>v;
for(int i = 1; i <= n; ++i){
tr[i].c = IntRead();tr[i].w = IntRead();tr[i].s = IntRead();
}
dp[0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = v; j >= 1; --j)
for(int k = 1;k <= tr[i].s; ++k){
if(j >= k * tr[i].c)
dp[j] = max(dp[j], dp[j - k * tr[i].c] + k * tr[i].w);
}
cout<<dp[v]<<endl;
return 0;
}
对于多重背包来说，你是得进行优化滴，不然怎么拿的出手呀，比赛的时候要死因为不进行优化而wa掉，可是会收到来自队友的亲切问候(>_<)
我们再捋一遍，不进行优化时，我们可以构造另外一个数组，在这个数组里面，每个物品只有一个，不过可以是相同的，也就是将k个物品a，拆开成k个放进新的数组，这样就会让物品数量急剧上升，然后在此基础上打暴力，会喜提TLE
所以我们就对次进行优化，既然不能一个一个放，那我们就进行二进制打包，拆成 1 2 4 8 ……等，最后余下的部分也打包进数组，这样做的好处是极大的减少了数组的长度，而且还可以通过某些方式凑出你需要的所有数量（数量小于给的数量）
嗯对，就是这个亚子滴
见代码叭
#inlcude<bits/stdc++.h>
using namespace std;
#define MAX 2000 + 7
int n, v, x, y, z, cnt;
vector<int>c;
vector<int>w;
int dp[MAX];
int main(){
cin>>n>>v;
for(int i = 1; i <= n; ++i){
cnt = 1;
cin>>x>>y>>z;
//对于每个数量进行拆分
while (z - pow(2, cnt) + 1 >= 0) {
c.push_back(x * pow(2, cnt - 1));w.push_back(y * pow(2, cnt - 1));//将拆好的大包进vector数组中
cnt++;
}
//特判有木有剩下滴，有的话就也打包进vector
if(z - pow(2, cnt - 1) + 1 != 0){
c.push_back(x * (z - pow(2, cnt - 1) + 1));w.push_back(y * (z - pow(2, cnt - 1) + 1));
}
}
//再就是简单的一维优化
for(int i = 0; i < c.size(); ++i)
for(int j = v; j >= c[i]; --j){
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
cout<<dp[v]<<endl;
return 0;
}
时间复杂度：
一般来说复杂度到这一步已经很优秀了，出题人很少会继续再卡你，一方面这个复杂度不太好卡，另一方面他脑子应该是没卡屎。但还是有其他的优化方法，比如单调队列的，虽然我没看（下次一定下次一定(>_<)
混合背包
在01背包的基础上，增加重量这一限制因素
1061.采药3
思路：
增加了一个条件我们就可以在原来的基础上去增加一个维度的数组来代表新的条件
状态：
状态转移方程：
#inlcude<bits/stdc++.h>
using namespace std;
#define MAX 100 + 7
int n, m, v;//n数量，m重量，v体积
struct ran{
int c, g, w;//c体积g重量w价值
}tr[MAX];
int dp[MAX][MAX];
int main(){
cin>>m>>v>>n;
for(int i = 1; i <= n; ++i)cin>>tr[i].g>>tr[i].c>>tr[i].w;
for(int i = 1; i <= n; ++i)
for(int j = v; j >= tr[i].c; --j)
for(int k = m; k >= tr[i].g; --k){
dp[j][k] = max(dp[j][k], dp[j - tr[i].c][k - tr[i].g] + tr[i].w);
}
cout<<dp[v][m]<<endl;
return 0;
}
分组背包
分组背包就如同字面意思，不同的物品有各自的分组，每个组最多只能选1个，问你能获得的最大价值是多少
确定状态：
之前的01背包中的i是指前i个物品，现在只是将其换成了组，道理差不多，我们只需要在此基础上去写个循环遍历每个组，看看选哪个好即可
状态转移方程：
其中的 i 指的是前 i 组，j指的是体积，k指的是对于第i组选第k个物品
c指的是体积，w指的是价值
P1757 通天之分组背包
#inlcude<bits/stdc++.h>
using namespace std;
#define MAX 1000 + 7
int n, v, a, b, d, m;
struct ran{
int c[MAX];//记录该组中的所有物品的体积
int w[MAX];//记录该组中的所有物品的价值
int cnt;//记录该组中物品数量
}tr[MAX];//不同的组
int dp[MAX];
int main(){
cin>>v>>n;
m = -1;
for(int i = 1; i <= n; ++i){
cin>>a>>b>>d;
m = max(m, d);//记录一共有多少组
tr[d].c[++tr[d].cnt] = a;//第d组的物品数增加一，且记录新元素的体积和价值
tr[d].w[tr[d].cnt] = b;
}
for(int i = 1; i <= m; ++i)//枚举每个组
for(int j = v; j >= 0; --j)
//从0开始枚举k，0是不选
for(int k = 0; k <= tr[i].cnt; ++k){
//这里一定要注意，之前的01背包都是在第二个循环写条件的地方判掉了j 与 目前物品的体积，而现在写第二个循环的时候并没有确定选哪个，所以并不能确定j取到哪里，故需要在此进行特判！！！
if(j >= tr[i].c[k])
dp[j] = max(dp[j], dp[j - tr[i].c[k]] + tr[i].w[k]);
}
cout<<dp[v]<<endl;
return 0;
}
P1064 [NOIP2006 提高组] 金明的预算方案
题意：
n块钱，m个物品，物品有主次之分，一个主件有0到两个次件，买主件可以选择买任意的次件，但不能单买次件，问你不超过n元的情况下，获得的最大重要度和价格的乘积最大为多少？
思路：
这个题其实是一个分组背包(#ﾟДﾟ)
对于每个主次组，只有四种情况：主，主+次1， 主+次2 ，主加次1 + 次2，相当于分组背包中每个组最多有四组，我们只需要对输入的数据进行处理和分组，然后再进行分组背包的操作即可
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 40000 + 7
#define endl '\n'
//#define mod 571373;
typedef long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, v, x, y, z;
struct ran{//结构体，用来存每个组的四种情况
int wei[5];//每个物品的体积
int val[5];//每个物品的价格和重要度的乘积
int cnt;//数量，用于最后的循环
}tr[65];
int dp[MAX];
int main(){
cin>>v>>n;
for(int i = 1; i <= n; ++i){
cin>>x>>y>>z;
if(z == 0){//如果是0，就说明是主件
tr[i].wei[1] = x;
tr[i].val[1] = y * x;
tr[i].cnt++;
}
else {//其他的都是附件，对附件的情况进行讨论
//特别注意，这下面的位置是z，不是i了！
if(tr[z].cnt == 1){//如果只有一个元素，说明该组目前只有一个主件，就往里面填入主+次1这个元素
tr[z].cnt++;
tr[z].wei[2] = tr[z].wei[1] + x;
tr[z].val[2] = tr[z].val[1] + y * x;
}
else{//往里面添加主 + ci2， 主 + 次1 + 次2
tr[z].cnt = 4;
tr[z].wei[3] = tr[z].wei[1] + x;
tr[z].val[3] = tr[z].val[1] + y * x;
tr[z].wei[4] = tr[z].wei[2] + x;
tr[z].val[4] = tr[z].val[2] + y * x;
}
}
}
for(int i = 1; i <= n; ++i){
for(int j = v; j >= 0; --j){
for(int k = 1; k <= tr[i].cnt; ++k){
if(j >= tr[i].wei[k]){
dp[j] = max(dp[j], dp[j - tr[i].wei[k]] + tr[i].val[k]);
}
}
}
}
cout<<dp[v]<<endl;
}
写在最后
这些是我通过学雨巨的视频，再参考了一些博客以后写出来的，主要是看的视频，所以可能会有小错误，望斧正
