01背包
问题描述
有N件物品和一个容量为V的背包。第i件物品的体积是weight[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和最大。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=100;
int weight[Maxsize];//每个物品的重量
int value[Maxsize];//每个容量的价值
int s[Maxsize];//每个状态的最大价值
int n;//物品的个数
int v;//背包容量
void dp(){
for(int i=0;i<n；i++){
for(int j=v;j>=weight[i];j--){
s[j]=max(s[j],s[j-weight[i]]+value[i]);
}
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
scanf("%d%d",&weight,&value);
}
dp();
printf("%d",s[v]);
return 0;
}
完全背包
问题描述
有N种物品和一个容量为V的背包，每种物品都有无限件可用。
第i种物品的体积是w，价值是v。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize];//每个物品的重量
int value[Maxsize];//每个武平的价值
int s[Maxsize];//每个状态的最大值
int n;//物品的个数
int v;//背包的容量
void dp(){
for(int i=0;i<n;i++){
for(int j=v-w[i];j<=v;j++)
s[j]=max(s[j],s[i-w[i]])
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
scanf("%d%d",&weight[i],&value[i]);
}
dp();
printf("%d",s[v]);
return 0;
}
分组背包
问题描述
有容积为V的背包，有n件物品，每种物品属于的组别不同，t为最大的组数，每组中的物品相互冲突，所以只能选其中一件接下来是每件物品的重量w[i],价值v[i],以及组号x，求最大的价值.
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize][Maxsize];//每个组的每个物品的重量
int value[Maxsize][Maxsize];//每个组的每个物品的价值
int s[Maxsize];//每个状态的最大价值
int t;//分组个数
int n;//物品个数
int v;//背包容量
void dp(){
for(int i=1;i<=t;i++){
for(int k=v;k>=1;k--)
for(int j=1;j<=weight[i][0];j++)
if(k>=weight[i][j])
s[k]=max(s[k],s[k-weight[i][j]]+value[i][j]);
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
int g,x,y;
scanf("%d%d%d",&g,&x,&y);
weight[g][0]++;//记录每个组的物品数量
value[g][0]++;
weight[g][weight[g][0]]=x;
value[g][value[g][0]]=y;
}
dp();
printf("%d",s[t]);
return 0;
}
混合背包
问题描述
有一个体积为V的背包，有m种物品，每种物品有体积和价值，且数量一定。求背包能装下的最大价值。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize];//每个物品的重量
int value[Maxsize];//每个物品的价值
int num[Maxsize];//每个物品的数量
int s[Maxsize];//每个状态的最大值
int n;//物品种数
int v;//背包容量
void dp(){
for(int i=0;i<n;i++){
if(num[i]==1)
for(int j=v;j>=v-weight[i];j--){
s[j]=max(s[j],s[j-weight[i]]+value[i]);
else if(num[i]<=(v/weight[i]))
for(int j=v;j>=1;j--)
for(int k=0;k<=num[i];k++)
if(j>=k*weight[i])
s[i]=max(s[j],s[j-k*weight[i]]+k*value[i]);
else
for(int j=v-weight[i];j<=v;j++)
s[i]=max(s[j],s[j-weight[i]]);
}
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
scanf("%d%d%d",&weight[i],&value[i],&num[i]);
}
dp();
printf("%d",s[v]);
return 0;
}
依赖背包
问题描述
有两种物品，一个为主件，一个为附件，附件依赖于主件，只有购买了主件才能购买附件，要购买附件必须购买相应的主件。每个物品有相应的重量和价值，现有一个容量为V的背包，求背包能装下的最大价值。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int mweight[Maxsize];//每个主件的重量
int mvalue[Maxsize];//每个主件的价值
int weight[Maxsize][Maxsize];//每个主件的每个附件的重量
int value[Maxsize][Maxsize];//每个主件的每个附件的价值
int s[Maxsize];//每个状态的最大价值
int n;//物品的个数
int v;//背包的容量
void dp(){
int tmpw,tmpv;
for(int i=1;i<=mweight[0];i++){//mweight[0]记录了主件的个数
tmp=mweight[i];
tmpv=mvalue[i];
for(int j=v;j>=tmp;j--)
s[j]=max(s[j],s[j-tmp]+mvalue[i]);
for(int j=1;j<=weight[i][0];j++){
tmpw+=weight[i][j];
tmpv+=value[i][j];
for(int k=v;k>=tmpw;k--)
s[k]=max(s[k],s[k-tmpw]+tmpv);
}
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
int p,q,r;
scanf("%d%d%d",&p,&q,&r);
if(r==0){
mweight[0]++;
mvalue[0]++;
mweight[mweight[0]]=p;
mvalue[mvalue[0]]=q;
}
else{
weight[r][0]++;
value[r][0]++;
weight[r][weight[r][0]]=p;
value[r][value[r][0]]=q;
}
}
dp();
printf("%d",s[v]);
return 0;
}
二维背包
问题描述
对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a和b。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize];//每个物品的重量
int price[Maxsize];//每个物品的价格
int value[Maxsize];//每个物品的价值
int s[Maxsize][Maxsize];//每个状态的最大价值
int n;//物品数量
int v;//背包容量
int u;//持有金钱
void dp(){
for(int i=0;i<n;i++){
for(int j=v,k=u;j>=weight[i]&&k>=price[i];j--,k--)
s[j][k]=max(s[j][k],s[j-weight[i]][k-price[i]]+value[i]);
}
}
int main(){
scanf("%d%d%d",&n,&v,&u);
for(int i=0;i<n;i++){
scanf("%d%d%d",&weight[i],&price[i],&value[i]);
}
dp();
printf("%d",s[v][u]);
return 0;
}
多重背包
问题描述
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize];//每种物品的重量
int value[Maxsize];//每种物品的价值
int num[Maxsize];//每种物品的数量
int s[Maxsize];//每个状态的最大价值
int n;//物品种数
int v;//背包容量
void dp(){
for(int i=0;i<n;i++){
for(int j=v;j>=1;j++)
for(int k=1;k<=num[i];k++)
if(j>=k*weight[i])
s[j]=max(s[j],s[j-k*weight[i]]+k*value[i]);
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
scanf("%d%d%d",&weight[i],&value[i],&num[i]);
}
dp();
printf("%d",s[v]);
return 0;
}
方案背包
问题描述
有N件物品和一个容量为V的背包。第i件物品的体积是weight[i]。求将背包装满的方案数。
实现代码
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000+10;
int weight[Maxsize];//每个物品的重量
int s[Maxsize][Maxsize];//记录每个状态的方案数
int n;//物品个数
int v;//背包容量
void dp(){
s[0]=1;
for(int i=0;i<n;i++){
for(int j=v;j>=weight[i];j--)
s[i][j]=s[i-1][j]+s[i-1][j-weight[i]];
}
}
int main(){
scanf("%d%d",&n,&v);
for(int i=0;i<n;i++){
scanf("%d",&weight[i]);
}
dp();
printf("%d",s[n-1][v]);
return 0;
}