背包复习
2025-05-05 19:58:08
发布于：上海
8阅读
0回复
0点赞
一共四种背包模型：
1、01背包
题面：
有n个物品，背包容量为m，第i件物品价格为c[i],价值是v[i]
每个物品只能那一次
求哪些物品放入背包能使得获得价值最大
思路：
每件物品可以选择放或不放
状态转移：每次从i,j的正上方和左上方转移过来
不放：dp[i][j] = dp[i-1][j];
放：dp[i][j] = dp[i-1][j-c[i]] + v[i];
最终的状态方程为：
if(j >= c[i])
dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]] + v[i]);
2、完全背包
题意：
有n个物品，背包容量为m，第i件物品价格为c[i],价值是v[i]
每个物品可以拿无数次
求哪些物品放入背包能使得获得价值最大
思路：
借鉴01背包：每个物品可以放或不放
状态转移：
放：dp[i][j] = dp[i-1][j];
不放：dp[i][j] = dp[i][j-c[i]]+v[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j] = max( dp[i-1][j] , dp[i][j-c[i]] + w[i] );
}
}
3、多重背包
题意：
有n个物品，背包容量为m，第i件物品价格为c[i],价值是v[i]，每件物品可以拿p[i]次
0 <= p[i] <= x
当p[i] = 0 时，可以取无限次
求哪些物品放入背包能使得获得价值最大
思路：
当p[i] = 0，可以当作完全背包来处理。
当p[i] = 1，可以当作01背包来处理。
当p[i] > 1，转化为多重背包。
状态转移：
for(int i=1;i<=n;i++){
if(p[i] == 0)
//参考完全背包
else{
//多重背包
for(int k=1;k<=p[i];k++)
for(int j=0;j<=m;j++)
dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]+w[i]);
}
}
二进制优化：
拆成：1，2，4，8，16......，和剩下的
for(int i=1;i<=n;i++){
int k = 1;
while(k <= p[i]){
int cost = c[i] * k;
int val = v[i] * k;
if(cost > m)break;
//视作01背包
for(int j=0;j<=m;j++)
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost]+val);
/*
for(int j=m;j>=0;j--)
dp[j] = max(dp[j],dp[j-cost]+val);
*/
p[i] -= k;
k *= 2;
}
if(p[i] > 0){
int cost = c[i] * p[i];
int val = v[i] * p[i];
if(cost > m)continue;
//视作01背包
for(int j=0;j<=m;j++)
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost]+val);
/*
for(int j=m;j>=0;j--)
dp[j] = max(dp[j],dp[j-cost]+val);
*/
}
}
4、分组背包
题意：
有n个物品，有T组，每个物品属于不同的组，背包容量为m，第i件物品价格为c[i],价值是v[i]，每件物品属于t[i]种类别
每组只能拿一个物品。
求哪些物品放入背包能使得获得价值最大
思路：
先将不同的物品分类
对于每组物品，用01背包求能拿到的最大价值。
状态转移：
#include<bits/stdc++.h>
using namespace std;
int v1,n,t;
struct node{
int w,v;
};
int dp[15][205];//第i组,容量为j的最大价值
vector<node> v[15];//用二维vector数组进行储存数据
int main(){
cin>>v1>>n>>t;
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
v[c].push_back({a,b});
}
for(int i=1;i<=t;i++){
for(int j=0;j<=v1;j++){
dp[i][j] = dp[i-1][j];//提前计算不放入的情况
for(int k=0;k<v[i].size();k++){//k遍历某一组物品的数量 0 ~ v[i].size()-1
if(j >= v[i][k].w)
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k].w]+v[i][k].v);
}
}
}
//答案
cout<<dp[t][v1];
return 0;
}
这里空空如也
有帮助，赞一个