背包

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;
}