algorithm/source/knapsackUnlimited.cpp at main · butcher-x/algorithm · 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
//
// Created by ButcherX on 23-12-9.
//
#include<iostream>
#include<vector>
using std::vector;
#include <chrono>
//每一种都尝试
int knapSackUnlimited(vector<int> weight, vector<int> value, int capacity)
{
    if(capacity < 0)
        return 0;
    int maxVal = 0;
    for(int i = 0; i < weight.size(); i++)
    {
        int val = 0;
        if(weight[i] <= capacity)//容易忽略
            val = value[i] + knapSackUnlimited(weight, value, capacity - weight[i]);
        maxVal = maxVal > val ? maxVal : val;
    }
    return maxVal;
}
//===================================================================
//动态规划
int knapSackUnlimited1(vector<int> weight, vector<int> value, int capacity)
{
    vector<int> dp(capacity + 1, 0);
    for(int c = 0; c <= capacity; c++)
    {
        int maxVal = 0;
        for(int i = 0; i < weight.size(); i++)
        {
            int val = 0;
            if(weight[i] <= c)
                val = value[i] + dp[c - weight[i]];
            maxVal = maxVal > val ? maxVal : val;
        }
        dp[c] = maxVal;
    }
    return dp[capacity];
}

///==========================================================================
//去重
int knapSackUnlimited4(vector<int> weight, vector<int> value, int capacity, int index)
{
    if(capacity < 0 || index >= weight.size())
        return 0;
    int max = 0;
    for(int i = 0; i * weight[index] <= capacity; i++)
    {
        int ret = knapSackUnlimited4(weight, value, capacity - weight[index] * i, index + 1);
        max = max > (i * value[index] + ret) ? max : (i * value[index] + ret);
    }
    return max;
}
//动态规划
int knapSackUnlimited5(vector<int> weight, vector<int> value, int capacity)
{
    vector<vector<int>> dp(capacity + 1, vector<int>(weight.size(), 0));
    for(int c = 0; c <= capacity; c++)
    {
        for(int index = weight.size() - 1; index >= 0; index--)
        {
            int max = 0;
            for(int i = 0; i * weight[index] <= c; i++)
            {
                int ret = index+1 > weight.size() ? 0 : dp[c-weight[index]*i][index+1];
                max = max > (i * value[index] + ret) ? max : (i * value[index] + ret);
            }
            dp[c][index] = max;
        }
    }
    return dp[capacity][0];
}
///===========================================================================
//从左到右
int process(vector<int> weight, vector<int> value, int index, int capacity)
{
    if(index >= weight.size() || capacity < 0)
        return 0;
    int ret1 = process(weight, value, index + 1, capacity);//不要此货物
    int ret2 = 0;
    if(weight[index] <= capacity)//当前容量够,才能要此货物
        ret2 = value[index] + process(weight, value, index, capacity - weight[index]);//要此货物
    return std::max(ret1 , ret2);
}
int knapSackUnlimited2(vector<int> weight, vector<int> value, int capacity)
{
    if(weight.size() != value.size())
        return 0;
    return process(weight, value, 0, capacity);
}
///==========================================================================
int knapSackUnlimited3(vector<int> weight, vector<int> value, int capacity)
{
    vector<vector<int>> dp(weight.size(), vector<int>(capacity + 1, 0));
    int last = weight.size() - 1;

    //特例初始化
    for(int c = 0; c <= capacity; c++)
    {
        if(weight[last] <= c)
            dp[last][c] = value[last];
    }

    //依次打表
    for(int i = weight.size() - 2; i >= 0; i--)
    {
        for(int c = 0; c <= capacity; c++)
        {
            int ret1 = dp[i+1][c];
            int ret2 = 0;
            if(weight[i] <= c)
                ret2 = value[i] + dp[i][c-weight[i]];
            dp[i][c] = std::max(ret1, ret2);
        }
    }
    return dp[0][capacity];
}
int main()
{
    vector<int> value  = {21,43,12,22,12,53,21,34,1};
    vector<int> weight = {14,23,54,33,11,33,7,24,2};
    int capacity = 50;
    std::cout << knapSackUnlimited1(weight, value, capacity) << std::endl;
    std::cout << knapSackUnlimited5(weight, value, capacity) << std::endl;

}