Algorithm-Notes-Practice/11_CompleteBag.cpp at master · CS0522/Algorithm-Notes-Practice · GitHub

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 * P446 完全背包问题
 * 动态规划
 * 每种物品都有无穷件
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// weight array
int *weight;
// value array
int *value;
// dp array
// 前 i 件物品恰好装入容量为 v 的背包中，所能获得的最大价值
int **dp;
// improved dp array
int *dpImprove;

// init
void init(int &num, int &maxV)
{
    weight = new int[num + 1];
    value = new int[num + 1];
    dp = new int*[num + 1];
    dpImprove = new int[maxV + 1];
    for (int i = 0; i <= num; i++)
    {
        dp[i] = new int[maxV + 1];
    }
    cout << "Input weight: " << endl;
    // input weight
    for (int i = 1; i <= num; i++)
    {
        cin >> weight[i];
    }
    cout << "Input value: " << endl;
    // input value
    for (int i = 1; i <= num; i++)
    {
        cin >> value[i];
    }
}

// main function
void calMaxVal(int &num, int &maxV)
{
    // 边界
    for (int v = 0; v <= maxV; v++)
    {
        dp[0][v] = 0;
    }
    // 状态转移
    for (int i = 1; i <= num; i++)
    {
        for (int v = weight[i]; v <= maxV; v++)
        {
            // 不放 i，放 i
            dp[i][v] = max(dp[i - 1][v], dp[i][v - weight[i]] + value[i]);
        }
    }
}

// improve space complexity
void calMaxValImprove(int &num, int &maxV)
{
    // 边界
    for (int v = 0; v <= maxV; v++)
    {
        dpImprove[v] = 0;
    }
    // 状态转移
    for (int i = 1; i <= num; i++)
    {
        // 完全背包问题，需要正序
        // 必须保证 [v - weight[i]] 是更新后的值
        for (int v = weight[i]; v <= maxV; v++)
        {
            dpImprove[v] = max(dpImprove[v], dpImprove[v - weight[i]] + value[i]);
        }
    }
}

// print result
void print(int &num, int &maxV)
{
    int result = 0;
    for (int i = 1; i <= num; i++)
    {
        for (int v = weight[i]; v <= maxV; v++)
        {
            if (dp[i][v] > result)
            {
                result = dp[i][v];
            }
        }
    }

    cout << "Max value is: " << result << endl;
}

void printImprove(int &num, int &maxV)
{
    int result = 0;
    for (int v = 0; v <= maxV; v++)
    {
        if (dpImprove[v] > result)
        {
            result = dpImprove[v];
        }
    }

    cout << "Max value is: " << result << endl;
}

int main()
{
    cout << "Input the number of matters and the max volume: ";
    int num, maxV;
    cin >> num >> maxV;
    init(num, maxV);
    // calMaxVal(num, maxV);
    // print(num, maxV);
    calMaxValImprove(num, maxV);
    printImprove(num, maxV);
    return 0;
}