感谢https://blog.csdn.net/Hearthougan/article/details/53869671

文章目录

只许选一次的背包 –– 0-1背包可以选无数次的背包 –– 完全背包数量有上限的背包 –– 多重背包三种背包开大会 –– 混合背包

只许选一次的背包 –– 0-1背包

问题描述

有$N$个物品和一个容量为$S$的背包，第$i$件物品的重量是$w[i]$，价值是$v[i]$。在每种物品只许放一次，不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。

思路

我们将$c(i,j)$定义为在前$i$个物品里做出选择，使容量为$j$的背包价值最大。

对于第$i$件物品，有两种情况:

1.放物品$i$，此时$c(i,j)=c(i-1,j-w[i])+v[i]$ 2.不放物品$i$，此时$c(i,j)=c(i-1,j)$

取最大值即可

综上所述，本题的状态转移方程为：$c(i,j)=maxc(i-1,j-w[i])+v[i],c(i-1,j)$。

伪代码如下：

for 1...n//遍历物品 for w[i]...s//背包容量 c[i][j]=max{c[i-1][j-w[i]]+v[i],c[i-1][j]}

优化优化再优化

这个思路时间上是最优的，但是空间可以优化到$O(V)$。

毕竟$c(i,j)$只跟上一行有关系，那么我们可以试试只用一维数组去储存。

这种方法可不可行？可行，但是$j$要逆向枚举，因为旧数据不能被覆盖。

我们来模拟试一下。

假如我们有五个数据，每个数据都依赖于上一行的前一个位置。

我们把红色当做旧数据，蓝色当做新数据。

接下来我们跑一遍 ——

红 红 红 红 红

红 红 红 红 蓝

红 红 红 蓝 蓝

红 红 蓝 蓝 蓝

红 蓝 蓝 蓝 蓝

蓝 蓝 蓝 蓝 蓝

很明显，这个过程中没有出现数据覆盖的现象，每一步计算，蓝色前面的都是它所依赖的红色。

在正着走一遍 ——

红 红 红 红 红

蓝 红 红 红 红

蓝 蓝 红 红 红

很明显，到这一步就出问题了 —— 第二步的计算前面的数据已经被覆盖成蓝色了！用的是同一行的数据！

再回到背包问题，如果正向枚举的话，原先的$c(i-1,j-w[i])$已经被覆盖了，现在里面装的是$c(i,j-w[i])$。这时极有可能已经选中了物品$i$，如果这次物品$i$还被选中的话，物品$i$就被选中了两次，违背了0-1背包的限制！

因此，为了不违背0-1背包的限制，我们必须逆向枚举。

优化后的伪代码如下:

for 1...n for s...w[i] c[i]=max{c[j-w[i]]+v[i],c[j]}

例题

开心的金明 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]。 请你帮助金明设计一个满足要求的购物单。 【输入格式】 输入的第1行，为两个正整数N,M，用一个空格隔开：（其中n（n<30000）表示总钱数，m(m<25)为希望购买物品的个数。） 从第2 行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v，p （其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5）） 【输出格式】 输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900

本题代码

#include<iostream> #include <algorithm> using namespace std; struct thing { int v,p; } want[30]; long long c[10010],d[10010]; int main() { int n,m; cin>>n>>m; for(int i=1; i<=m; i++) { cin>>want[i].v>>want[i].p; }//读入不解释 for(int i=1; i<=m; i++) {//枚举物品 for(int j=n; j>=want[i].v; j--) {//背包重量逆向循环 c[j]=max(c[j],c[j-want[i].v]+want[i].v*want[i].p);//状态转移 } } cout << c[n] << endl; return 0; }

可以选无数次的背包 –– 完全背包

问题描述

有$N$个物品和一个容量为$S$的背包，第$i$件物品的重量是$w[i]$，价值是$v[i]$。在每种物品有无限个，不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。

思路 此题和0-1背包问题很像，所以可以在0-1背包的基础上做一定的修改就可以了。

想想看，0-1背包在哪里阻止了重复选择物品的可能？

当然是$j$的循环这个地方！

那么，我们直接把$j$的循环这个地方改成正序（可能重复装入物品，正好满足要求）不就可以了吗？

完整代码 如下（找不到例题QAQ）

#include<iostream> #include<algorithm> using namespace std; struct thing { int v,p; } want[30]; long long c[10010]; int main() { int n,m,; cin>>n>>m; for(int i=1; i<=m; i++) { cin>>want[i].v>>want[i].p; } //读入 for(int i=1; i<=m; i++) {//枚举物品 for(int j=want[i].v;j<=n; j++) { //背包容量正序循环 c[j]=max(c[j],c[j-want[i].v]+want[i].p); //状态转移 } } cout << c[n] << endl; return 0; }

数量有上限的背包 –– 多重背包

问题描述

有$N$个物品和一个容量为$S$的背包，第$i$件物品的重量是$w[i]$，价值是$v[i]$，上限是$x[i]$。在不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。

此题和0-1背包问题也很像，所以也可以在0-1背包的基础上做一定的修改。

我们可以直接加一个循环，从0到上限枚举物品个数，伪代码如下：

for 1...n for s...w[i] for 0...x[i] if j>=w[i]*k c[j]=max{c[j-w[i]*k]+v[i]*k,c[j]}

例题

庆功会 为了庆祝班级在全校运动会上取得全校第一名的成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能够买最大值的奖品，可以补充他们的精力和体力。 【输入格式】 第一行两个数n（≤500），m（≤6000），分别代表奖品种数和拨款金额。 接下来n行，每行三个数v，p，s，分别代表奖品价格，价值和能够买到的最大数量，其中v≤100，p≤1000，s≤10。 【输出格式】 一个数，表示此次购买能获得的最大价值。 【输入样例】 5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1 【输出样例】 1040

代码

如下

#include<iostream> #include<algorithm> using namespace std; struct thing { int v,p,x; } want[30]; long long c[10010]; int main() { int n,m; cin>>n>>m; for(int i=1; i<=m; i++) { cin>>want[i].v>>want[i].p>>want[i].x; } //读入 for(int i=1; i<=n; i++) { //枚举物品 for(int j=m;j>=want[i].v; j--) {//背包容量逆序循环 for(int k=0;k<=want[i].x; k++){//枚举物品个数 if(j >= k*want[i].v)//是否够装 c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p); //状态转移 } } } cout << c[m] << endl; return 0; }

三种背包开大会 –– 混合背包

问题描述

有$N$个物品和一个容量为$S$的背包，第$i$件物品的重量是$w[i]$，价值是$v[i]$，上限是$x[i]$（若为$0$则可取无限个）。在不可拆分，不超过背包容量的前提下，问如何才能让背包的总价值最大。

如果有了三种背包的基础，这道题就很简单了，伪代码如下：

for 1...n if x[i]==0//完全背包 for w[i]...s c[j]=max{c[j-w[i]]+v[i],c[j]} else//0-1背包和多重背包 for s...w[i] for 0...x[i] if j>=w[i]*k c[j]=max{c[j-w[i]*k]+v[i]*k,c[j]}

完整代码

如下

#include<iostream> #include<algorithm> using namespace std; struct thing { int v,p,x; }want[30]; long long c[10010]; int main() { int n,m; cin>>n>>m; for(int i=1; i<=m; i++) { cin>>want[i].v>>want[i].p>>want[i].x; }//读入 for(int i=1; i<=n; i++) {//枚举物品 if(want[i].x == 0){//完全背包 for(int j=want[i].v;j<=m;j++)//背包容量正序循环 c[j]=max(c[j-w[i]]+v[i],c[j]);//状态转移 }else{//0-1和多重背包 for(int j=m;j>=want[i].v; j--) {//背包容量逆序循环 for(int k=0;k<=want[i].x; k++){//枚举个数 if(j >=k*want[i].v)//够装吗？ c[j]=max(c[j],c[j-k*want[i].v]+k*want[i].p);//状态转移 } } } } cout << c[m] << endl; return 0; }

附： 0-1背包空间和时间都最优的代码

#include <iostream> #include <algorithm> using namespace std; int main(){ int n,s,f[100],w,v; cin>>n>>s; for(int i = 1;i <= n;i++) cin>>w>>v; for(int j = s; j >= w[i]; j--) f[j] = max(f[j], f[j-w]+v); cout<<f[s]<<endl; return 0; }

超级大礼包

https://www.luogu.com.cn/discuss/show/263072