混合背包

传送门

题面描述

【问题描述】
一个旅行者有一个最多能用 V 公斤的背包,现在有 n 件物品,它们的重量分别是 $ W_1,W_2,...,W_n $,它们的价值分别为 $ C_1,C_2,...,C_n $。有的物品只可以取一次(01 背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
【输入格式】
第一行:二个整数,V(背包容量,V<=200),N(物品数量,N<=30);
第 2..N+ 1 行:每行三个整数 Wi,Ci,Pi,前两个整数分别表示每个物品的重量,价值,第三个整数若为 0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多件数 (Pi)。
【输出格式】
仅一行,一个数,表示最大总价值。
【样例输入】
10 3
2 1 0
3 3 1
4 5 4
【样例输出】
11
【样例解释】
选第一件物品 1 件和第三件物品 2 件。

解题思路

这道题是完全背包和多重背包的合体。

只需要用一个新的数组,如果是多重,就分解,然后在另外一个数组中设其为 1。否则就直接放入那个数组,在另外一个数组中设其为 0。(其中 1 为有限,0 为无限的意思。)

在 dp 环节中,如果是有限,就用 01 背包的方法解它,否则就用多重背包的方法解它。

代码

#include <iostream>
using namespace std;
int main(){
    int v[100000],w[100000],s[100000];
    int n,m;
    cin>>n>>m;
    int vt,wt,ct,t;
    int cnt=1;
//分类+分解环节
    for(int i=0;i<m;i++){
        t=1;
        cin>>vt>>wt>>ct;
        if(ct!=0){
        while(ct>=t){
            v[cnt]=vt*t;
            w[cnt]=wt*t;
            s[cnt]=1; 
            cnt++;
            ct-=t;
            t*=2;
            
        }
        v[cnt]=vt*ct;
        w[cnt]=wt*ct;
        s[cnt]=1;
        cnt++;
        }else{
            v[cnt]=vt;
            w[cnt]=wt;
            s[cnt]=0;
            cnt++;
        }
    }
    int dp[100000];
    cnt--;
//dp环节
    for(int i=1;i<=cnt;i++){
        for(int j=n;j>=0;j--){
            if(s[i]==1){//当它是有限的物品情况下
                if(j>=v[i]){
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                }else{
                    dp[j]=dp[j];
                }
            }else if(s[i]==0){//当它是无限的物品的情况下
                for(int k=1;k<=n/v[i];k++){//枚举到取最多次的状态
                    if(j>=v[i]*k){
                        dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k);
                    }else{
                        dp[j]=dp[j];
                    } 
                }
            }
        }
    }
    cout<<dp[n];
    return 0; 
}
/*
10 4
2 1 0
3 3 1
4 5 4
2 0 1
*/