混合背包

传送门

题面描述

【问题描述】
一个旅行者有一个最多能用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
*/ 

本文链接:https://kaispace.com.cn/index.php/archives/342/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者