关于完全背包问题(入门) 笔记
2024-08-11 20:06:53
发布于:广东
完全背包问题
目录
1——问题概览
2——从"01背包"到"完全背包"
3——完全背包的优化
4——总结
问题概览
难度:普及
题目:
本文以YBT 1268 完全背包模板来作完全背包的讲解,另外两题同样为完全背包模版的应用,难度低,适合练习
描述:
设有种物品,每种物品有一个重量及一个价值。
但每种物品的数量是无限的,同时有一个背包,最大载重量为
今从种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于,而价值的和为最大。
从"01背包"到"完全背包"
同为背包问题,完全背包与01背包极其的相似
但不同的是01背包对问题描述是每个物品只能拿一次,对于物品也就有拿和不拿两种状态
完全背包是每个物品能拿任意次
在对01背包的讲解当中我们知道 (01背包-洛谷 01背包-ACGO)
01背包的状态转移方程当中
是对于第i个物品如果存放,那么它的价值为 操作前个物品且重量为时的最大值 加当前物品价值
这是01背包的,在完全背包中物品可以重复放
所以完全背包中对于第i个物品如果存放,它的价值为 操作前个物品且重量为时的最大值 加当前物品价值
即除此之外其它都与01背包一致!
完全背包Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205][205];//当操作物品数为i,背包容量为v时所获最大价值
ll maxn(ll x,ll y){
if(x>y){return x;}
else{return y;}
}
int main(){
memset(DP,0,sizeof DP);
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i].weight>>a[i].value;
}//输入
for(int i=1;i<=n;i++){//n件物品,每件物品可取任意次数
for(int v=1;v<=m;v++){//
if(a[i].weight>v){DP[i][v]=DP[i-1][v];}//当前物品重量大于容量,不放继承i-1
else{
DP[i][v]=maxn(DP[i-1][v],DP[i][v-a[i].weight]+a[i].value);//看放和不放哪个价值大
}//因为可以重复放,所以找的是当前轮即DP[i][v-a[i].weight]
}
}
cout<<"max="<<DP[n][m];
return 0;
}
完全背包的优化
既然对01背包可以进行优化,那么同样的完全背包也可以进行优化 把它的空间复杂度压缩成一维
在01背包的讲解文章中,我们对它优化后是进行逆推,如果进行顺推是错误的,这个我们也进行过讲解
但其实,完全背包的优化后推法就是顺推,对于01背包进行逆推就是为了保证每一件物品只可以选一次,顺推的结果会保存到同一轮的,而这正好符合完全背包的要求
因此完全背包优化后的代码也肥肠容易写出来
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct WC{ll weight,value;};//weight重量 value价值
ll n,m;//n件物品,m背包容量
WC a[205];//存储物品结构体数组
ll DP[205];//当背包容量为v时所获最大价值
ll maxn(ll x,ll y){
if(x>y){return x;}
else{return y;}
}
int main(){
memset(DP,0,sizeof DP);
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i].weight>>a[i].value;
}//输入
for(int i=1;i<=n;i++){//顺推n件物品,每件物品可取任意次数
for(int v=a[i].weight;v<=m;v++){
DP[v]=maxn(DP[v],DP[v-a[i].weight]+a[i].value);
//cout<<DP[v]<<' ';
} //cout<<endl;
}
cout<<"max="<<DP[m];
return 0;
}
总结
完全背包建立与01背包的基础之上,也由此可见01背包的重要性
两个问题的思维相似,建议配合食用
这里空空如也
有帮助,赞一个