背包问题
2025-05-03 16:32:27
发布于：上海
4阅读
0回复
0点赞
1、01背包
1.1题面：
有n个物品，背包容量为m,第i件物品费用为c[i],价值v[i],每一件物品只能拿一次。求那些物品放入背包总价值最大。
1.2思路：
每种一件，可选放/不放。
1.3状态转移方程：
每一次从i,j的正上方转移
不放： dp[i][j]=dp[i-1][j];
从上一个物品的同一个容量的最大价值继承过来
放：dp[i][j]=dp[i-1][j-c[i]]+v[i];
for(int j=m;j>=1;j++){
if(j>=c[i])dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
}
2、完全背包
1.1题面：
有n个物品，背包容量为m,第i件物品费用为c[i],价值v[i],每一件物品能拿无限次。求那些物品放入背包总价值最大。
1.2思路：
每种一件，可选放/不放。
1.3状态转移方程：
每一次从i,j的正上方转移
不放： dp[i][j]=dp[i-1][j];
从上一个物品的同一个容量的最大价值继承过来
放：dp[i][j]=dp[i-1][j-c[i]]+v[i];
for(int j=1;j<=m;j++){
if(j>=c[i])dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
}
3、混合背包
3.1 题意
有n个物品，背包容量为m
，第i件物品的费用是cos[i],价值是value[i],每件物品拿p[i]次,求那些物品放入背包总价值最大。
3.2 思路
当p[i]=0时->完全背包
当p[i]=1时->01背包
当p[i]>1时->多重背包
3.3 状态转移方程
for(int k=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]);
}
}
3.4 二进制优化
拆成1，2，4，8，……，和剩下的。合并成一个新的物品
for(int i=1;i<=n;i++){
int k=1;
while(k<=p[i]){
int cost=c[i]*k;
int value=v[i]*k;
//视作01背包处理
if(cost>m) break;
for(int j=1;j<=m;j++){
dp[i][j]=max(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];
//视作01背包处理
if(cost>m) continue;
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j-cost]+value);
}
}
}
4、分组背包
4.1 题意
有```n```个物品，有T组，每个物品属于不同的组。背包容量为```m```，第```i```件物品的费用为```cos[i] ```,价值是```value[i]```，第```i```个物品属于```t[i]```组。
每组只能拿一个物品。求拿哪些物品放入背包能使得价值最大
4.2 思路
先将不同的物品分类。对每一组物品，用01背包的方式求能拿的最大价值。
4.3 状态转移方程
分组背包_信奥算法题-ACGO题库
#include<bits/stdc++.h>
using namespace std;
struct node{
int w,c;
};
vector<node> v[15];
int V,n,t,dp[15][205];//第i组，容量为j的最大价值
int main(){
//输入
cin>>V>>n>>t;
for(int i=1;i<=n;i++){
int W,C,P;
cin>>W>>C>>P;
v[P].push_back({W,C});
}
for(int i=1;i<=t;i++){
for(int j=0;j<=V;j++){
dp[i][j]=dp[i-1][j];//不拿
for(int k=0;k<v[i].size();k++){//v[i].size() : 保存的是第i个vector的数组个数
if(j>=v[i][k].w) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][k].w]+v[i][k].c);
}
}
}
cout<<dp[t][V];
return 0;
}
滚动数组优化
#include<bits/stdc++.h>
using namespace std;
struct node{
int w,c;
};
vector<node> v[15];
int V,n,t,dp[15][205];//第i组，容量为j的最大价值
int main(){
//输入
cin>>V>>n>>t;
for(int i=1;i<=n;i++){
int W,C,P;
cin>>W>>C>>P;
v[P].push_back({W,C});
}
for(int i=1;i<=t;i++){
for(int j=V;j>=0;j++){
for(int k=0;k<v[i].size();k++){//v[i].size() : 保存的是第i个vector的数组个数
if(j>=v[i][k].w) dp[j]=max(dp[j],dp[j-v[i][k].w]+v[i][k].c);
}
}
}
cout<<dp[t][V];
return 0;
}
这里空空如也
有帮助，赞一个