Algorithm-Notes-Practice/11_01Bag.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
/**
 * P443 01 背包问题
 * 动态规划
*/

#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 - 1][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++)
    {
        // 逆序
        // 如果不逆序，就会使用左边已经更新的值
        // 结合二维数组版理解
        for (int v = maxV; v >= weight[i]; 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;
}