25.5.3笔记(vector+背包)
2025-05-10 13:48:29
发布于：上海
15阅读
0回复
0点赞
1.二维vector
vector<int> v[100];
v[0].push-back(1);v[0][0]=1;
2.结构体+vector
struct node{
int w,c;
};
vector<node> v[100];
v[0].push-back({1,10});
3.01背包
有n个物品 背包容量m 第i件物品费用c[i] 价值v[i]
每个物品只能拿一次
求拿哪些物品放入背包能使价值最大
思路：
每种只有一件 选择放或不放
状态转移方程：
每一次从i,j的正上方和左上方转移过来
i:1~n;j:1~m
不放：dp[i][j]=dp[i-1][j] 继承
放：dp[i-1][j-1]=dp[i-1][j-c[i]]+v[i]
if(j>=c[i])dp[i][j]=max(不放,放);
4.完全背包
每个物品可以无数次
思路借鉴01背包：放or不放
状态转移方程：
dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i];
5.1.多重背包
每个物品可以拿p[i]次 0<=p[i]<=x
思路：
p[i]=1 转化为01背包
p[i]>1 转化为多重背包
p[i]=0 转化为完全背包
状态转移方程
for(int i=1;i<=n;i++){
if(p[i]==0){
完全背包
}
else{
多重背包
for(int k=1;k<=p[i];k++){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
}
}
}
}
5.2.二进制优化
思路：
拆成1 2 4 8... 和剩下的 合并一个新的物品
例：
for(int i=1;i<=n;i++{
int k=1;//当前物品个数
while(k<p[i]){
int cost=k*c[i]
int value=k*v[i];
if(cost>m)break;
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost]+value);
}
p[i]-=k;
k*=2;
}
if(p[i]>0){
int cost=c[i]*p[i];
int value=v[i]*p[i];
if(cost>m)continue;
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost]+value);
}
}
}
6.分组背包
n个物品 T个组 背包容量m 第i件物品费用为cost[i] 价值为value[i] 每组只能拿1个物品 第i个物品属于t[i]组
思路：
先将不同的物品分类
对每一组物品 用01背包的方式求能拿的最大价值
例：
using namespace std;
struct node{
int w,c;
};
vector<node> v[100005];
int dp[100005];//第i组，容量为j
int main(){
//输入
int V,n,t;//背包容量 物品数量 最大组号
cin>>V>>n>>t;
for(int i=0,W,C,P;i<n;i++){
cin>>W>>C>>P;//重量 价值 所属组号
v[P].push_back({W,C});
}
//遍历顺序
for(int i=1;i<=t;i++){
for(int j=V;j>=0;j--){
//k要遍历某一组物品的数量
for(int k=0;k<v[i].size();k++){
//拿
if(j>=v[i][k].w)dp[j]=max(dp[j],dp[j-v[i][k].w]+v[i][k].c);
}
}
}
cout<<dp[V];
return 0;
}
这里空空如也
有帮助，赞一个