背包问题（2）

混合背包

问题描述：

有n种物品，每件物品的重量为w[i]，价值为v[i]。现有一个容量为C的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中有些物品只能取一次，有些物品可以取有限多次，有些物品可以取无限次。

问题分析：

这题其实就是0/1背包、完全背包、多重背包三种问题混合起来。

对每种物体进行一次判断，选择对应的状态转移方程即可

这三种背包问题的分析→背包问题（1）

代码实现：

#include<iostream>
using namespace std;
#define MAX_CAPATICY 100
#define MAX_QUANTITY 100
int w[MAX_QUANTITY+2];///物品重量
int v[MAX_QUANTITY+2];///物品价值
int m[MAX_QUANTITY+2];///第i种物品的件数,输入0表示无限件
int dp[MAX_QUANTITY+2];///使用一维数组
int c,n;///背包容量和物品数量
int main()
{
    while(cin>>c>>n){
        for(int i=1;i<=n;++i){
            cin>>w[i]>>v[i]>>m[i];
        }
        for(int i=1;i<=n;++i){
            if(m[i]==0||m[i]*w[i]>c){///如果此物品总重量超过背包容量 也当作完全背包
                for(int j=w[i];j<=c;++j){
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                }
            }
            else{///多重背包和0/1背包
                for(int j=c;j>=w[i];--j){
                    int k=1,num=m[i];
                    while(k<=num){
                        dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
                        num-=k;
                        k<<=1;
                    }
                    dp[j]=max(dp[j],dp[j-num*w[i]]+num*v[i]);
                }
            }
        }
        cout<<dp[c];
    }
    return 0;
}

二维背包

问题描述：

对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值分别为V和U。物品的价值为v[i]。

问题分析：

二维背包和0/1背包很像，只是加了一个费用条件

只需要多开一维数组来存储

参考0/1背包问题状态转移方程为：dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+v[i]

代码实现：

#include<iostream>
using namespace std;
#define MAX_CAPATICY 100
#define MAX_QUANTITY 100
int a[MAX_QUANTITY+2];///物品代价一
int b[MAX_QUANTITY+2];///物品代价二
int v[MAX_QUANTITY+2];///物品价值
int dp[MAX_QUANTITY+2][MAX_QUANTITY+2];///增加一维费用
int U,V,n;///背包代价一最大值、代价二最大值和物品数量
int main()
{
    while(cin>>U>>V>>n){
        for(int i=1;i<=n;++i){
            cin>>a[i]>>b[i]>>v[i];
        }
        for(int i=1;i<=n;++i){
            for(int j=U;j>=a[i];--j){
                for(int k=V;k>=b[i];--k){
                    dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+v[i]);
                }
            }
        }
        cout<<dp[U][V]<<endl;
    }
    return 0;
}

分组背包

问题描述：

有N件物品和一个最大承重为C的背包，已知这N件物品的重量w[i]以及价值v[i]，将这些物品划分为K组，每组中的物品互相冲突，最多选一件，求解将哪些物品装入背包可使这些物品的费用综合不超过背包的容量，且价值总和最大。

问题分析：

类比0/1背包，分组背包多了分组

对于每件物品还是两种选择，选或是不选

先对第一组第一个进行判断，选择的话就对下一组第一个进行判断，不选择就对本组下一个进行判断

代码实现：

#include<iostream>
using namespace std;
#define MAX_CAPATICY 100
#define MAX_QUANTITY 100
#include<vector>
int w[MAX_QUANTITY+2];///物品重量
int v[MAX_QUANTITY+2];///物品价值
vector<int> g[MAX_QUANTITY+2];///物品所在小组
int dp[MAX_QUANTITY+2];///使用一维数组
int c,n,t;///背包容量、物品数量和小组总数
int p;///物品所在小组
int main()
{
    while(cin>>c>>n>>t){
        for(int i=1;i<=n;++i){
            cin>>w[i]>>v[i]>>p;
            g[p].push_back(i);
        }
        for(int i=1;i<=t;++i){
            for(int j=c;j>=1;--j){
                for(int k=0;k<g[i].size();++k){///循环的顺序千万不能错
                    if(j>=w[g[i][k]]){
                        dp[j]=max(dp[j],dp[j-w[g[i][k]]]+v[g[i][k]]);
                    }
                }
            }
        }
        cout<<dp[c]<<endl;
    }
    return 0;
}