背包动态规划-多重背包

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

/**************************************************************** 
 * Description: C++ implementation of multiKnapsack 
 * Author: Alex Li
 * Date: 2023-06-20 10:53:09
 * LastEditTime: 2023-06-20 12:39:18
****************************************************************/
#include <iostream>
using namespace std;

const int MAXN=10000;//定义最大物品数量
const int MAXV=10000;//定义最大背包容量
int N; //物品数量
int V; //背包容量
int Weight[MAXN];  //存储每件物品的重量
int Value[MAXV];   //存储每件物品的价值
int dp[MAXV];      //滚动数组


//滚动数组解决01背包问题
void knapsack(int n){
    for(int i=0;i<=V;i++)dp[i]=0;
    for (int i = 1; i <=n; i++){
        for(int j=V; j>=Weight[i];j--)
           dp[j]=max(dp[j-Weight[i]]+Value[i],dp[j]);
    }
}

int main(){
    //实际物品的重量、价值和数量
    int realWeight[MAXN],realValue[MAXV],realNumber[MAXN];
    int k=0; //k是储存物品展开后的标号
    cin>>N>>V; //输入原始物品数量和背包容量。
    //输入N个物品的重量、价值和数量
    for(int i=1;i<=N;i++)cin>>realWeight[i]>>realValue[i]>>realNumber[i];
    
    /*把物品数量按二进制展开成多个物品
    比如A物品有20个，每个物品价值是3元，展开成如下：
    物品   数量   价值
    A1     1      3
    A2     2      6
    A3     4     12
    A4     8     24
    A5     5     15
    */
    
    for (int i =1; i <=N; i++){
        for (int j =1; j <=realNumber[i]; j<<=1){
            k++;
            Weight[k]=realWeight[i]*j;
            Value[k]=realValue[i]*j;
            realNumber[i]-=j;
        }
        if(realNumber[i]!=0){
        k++;
        Weight[k]=realWeight[i]*realNumber[i];
        Value[k]=realValue[i]*realNumber[i];
        }    
    }
    //经过二进制展开后，物品数量为k，对应每个物品的重量Weight[i]、价值Value[i]
    knapsack(k);
    cout<<dp[V];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-07 17:53:48
 * 最后修改: 2025-01-31 14:50:32
 * 文件描述: 多重背包问题
****************************************************************/

#include <iostream>
using namespace std;

const int MAXN=10000;//定义最大物品数量
const int MAXV=10000;//定义最大背包容量
int N; //物品数量
int V; //背包容量
int Weight[MAXN];  //存储每件物品的重量
int Value[MAXN];   //存储每件物品的价值
int dp[MAXN][MAXV]; //二维数组

void expandItems(int realNumber[MAXN], int &k, int realWeight[MAXN], int realValue[MAXN])
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= realNumber[i]; j <<= 1)
        {
            k++;
            Weight[k] = realWeight[i] * j;
            Value[k] = realValue[i] * j;
            realNumber[i] -= j;
        }
        if (realNumber[i] != 0)
        {
            k++;
            Weight[k] = realWeight[i] * realNumber[i];
            Value[k] = realValue[i] * realNumber[i];
        }
    }
}

//二维数组解决01背包问题
void knapsack(int n){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=V;j++){
            if(i==0 || j==0)
                dp[i][j] = 0;
            else if(Weight[i] <= j)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-Weight[i]] + Value[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
}

int main(){
    //实际物品的重量、价值和数量
    int realWeight[MAXN], realValue[MAXN], realNumber[MAXN];
    int k = 0; //k是储存物品展开后的标号
    cin >> N >> V; //输入原始物品数量和背包容量。
    //输入N个物品的重量、价值和数量
    for(int i = 1; i <= N; i++) cin >> realWeight[i] >> realValue[i] >> realNumber[i];
    
    /*把物品数量按二进制展开成多个物品
    比如A物品有20个，每个物品价值是3元，展开成如下：
    物品   数量   价值
    A1     1      3
    A2     2      6
    A3     4     12
    A4     8     24
    A5     5     15
    */

    expandItems(realNumber, k, realWeight, realValue);
    //经过二进制展开后，物品数量为k，对应每个物品的重量Weight[i]、价值Value[i]
    knapsack(k);
    //输出最大价值
    cout << dp[k][V] << endl;
    return 0;
}