1、背包问题--竞赛真理
每个物品有多种采用方式
http://www.rqnoj.cn/problem/160
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//每样物品有两种选择方法
//value[1] pri[1] value[2] pri[2]
int value[3][40],pri[3][40];
int f[1080002];
int n,t;
int main(){
scanf("%d %d",&n,&t);
for(int i=1;i<=n;i++){
scanf("%d %d %d %d",&value[1][i],&pri[1][i],&value[2][i],&pri[2][i]);
}
for(int i=1;i<=n;i++){
for(int j=t;j>0;j--){
for(int k=1;k<=2;k++){
if(j>pri[k][i]){
f[j]=max(f[j],f[j-pri[k][i]]+value[k][i]);
}
}
}
}
printf("%d
",f[t]);
return 0;
}
2、分组背包：金明的预算方案
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//有约束的背包问题
//在考虑主件的时候一起考虑附件
//当有1个附件的时候，有两种方案
//有2个附件的时候，有4中方案
int num[100];//有多少个东西
int f[100][100][3]; //第二维的时候数字（表示策略的种数），第三维 1 表示重要度*价值， 2 表示代价
int value[100],imp[100],q[100];
int n,m;
int dp[32001];
int type[100] ; //这个标识选取方法数
void pre(){ //预处理策略
for(int i=1;i<=m;i++){
if(num[i]==1){
type[i]=1; //只有主件
}
else if(num[i]==2){
//有一个附件
type[i]=2;
}
if(num[i]>=2){
//先处理2+主件
f[i][2][1]+=f[i][1][1];
f[i][2][2]+=f[i][1][2];
}
if(num[i]==3){
type[i]=4; //有两个附件
f[i][3][1]+=f[i][1][1];f[i][3][2]+=f[i][1][2]; //3+主件
f[i][4][1]=f[i][2][1]+f[i][3][1]-f[i][1][1]; //两个附件都带上
f[i][4][2]=f[i][2][2]+f[i][3][2]-f[i][1][2];
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&value[i],&imp[i],&q[i]);
if(!q[i]){
num[i]++;
f[i][1][1]=value[i]*imp[i];
f[i][1][2]=value[i];
}
else{
num[q[i]]++;
f[q[i]][num[q[i]]][1]=value[i]*imp[i];
f[q[i]][num[q[i]]][2]=value[i];
}
}
pre();
for(int i=1;i<=m;i++){
if(num[i]>=0){
for(int j=n;j>=0;j--){
for(int k=1;k<=type[i];k++){ //策略数
if(f[i][k][2]<=j){
dp[j]=max(dp[j],dp[j-f[i][k][2]]+f[i][k][1]);
}
}
}
}
}
printf("%d
",dp[n]);
return 0;
}
复习
- 01背包：每个东西只有一份
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){ //逆序
f[j]=max(f[j-w[i]]+c[i],f[j]); //这里是J
}
}
cout<<f[m]<<endl;
- 完全背包：每个东西可以取无限份
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
for(int i=1;i<=n;i++){//顺序
for(int j=w[i];j<=m;j++) if(f[j]<f[j-w[i]]+c[i]) f[j]=f[j-w[i]]+c[i];
}
cout<<"max="<<f[m]<<endl;
- 混合背包：有的物品有多个有的物品只有1个，分别进行处理，逆序or正序，注意选择多个的时候循环次序，物品数量在外层，背包重量在内层
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>s[i];
for(int i=1;i<=n;i++){
if(s[i]==0){ //完全背包，顺序
for(int j=w[i];j<=m;j++){
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
}
else {//01背包和多重背包，逆序
for(int j=1;j<=s[i];j++) //注意顺序，先是物品个数，再是剩余重量
for(int k=m;k>=w[i];k--)
f[k]=max(f[k],f[k-w[i]]+c[i]); //这里没有j噢
}
}
cout<<f[m]<<endl;
- 多重背包，可以通过二进制处理降低复杂度，原理是每个数都可以表示位2进制相加的形式，所以这样就把它处理为了01背包问题
-
int x,y,n1=0,s,t; for(int i=1;i<=n;i++){ cin>>x>>y>>s; t=1; while(s>=t){ w[++n1]=t*x; //重量 c[n1]=t*y; //价值 s-=t; t*=2; } w[++n1]=s*x; c[n1]=s*y; } //接下来就是01背包问题 for(int i=1;i<=n1;i++){ //注意数量 for(int j=m;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+c[i]); } } cout<<f[m]<<endl; - 二维背包问题：eg.潜水员
cin>>m>>n>>k;
memset(f,127,sizeof(f));//赋值为一个很大的数，因为是要求最小的
f[0][0] =0; //f[0][0]要初始化
for(int i=1;i<=k;i++) cin>>mm[i]>>nn[i]>>w[i];
for(int i=1;i<=k;i++){
for(int j=m;j>=0;j--){//都是01背包 费用1
for(int k=n;k>=0;k--){ //费用2
int t1=j+mm[i];
int t2=k+nn[i]; //注意写法 ，不能在外面直接判断
if(t1>m) t1=m;
if(t2>n) t2=n;
if(f[t1][t2]>f[j][k]+w[i]) f[t1][t2]=f[j][k]+w[i];
}
}
}
cout<<f[m][n]<<endl;
- 分组背包，背包分组，注意循环的顺序，最外层是组数，中间层是剩余的体积，最里层是这个组里面的物品序号
int p=0;
cin>>v>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i]>>p;
g[p][++g[p][0]]=i; //这种写法，合并了两个功能
}
for(int i=1;i<=k;i++){ //分的组数
for(int j=v;j>=0;j--){ //第二层是体积
for(int k=1;k<=g[i][0];k++){ //这个组的物品序号
if(j>=w[g[i][k]]){ //注意是>=，不然结果不正确
int temp=g[i][k];
if(f[j]<f[j-w[temp]]+c[temp]) f[j]=f[j-w[temp]]+c[temp];
}
}
}
}
cout<<f[v]<<endl;