揹包問題

0-1 揹包

當給出一組專案時，揹包問題是一個問題，每個專案都有一個權重，一個值和一個副本，確定要包含在一個集合中的哪個專案，以便總重量小於或等於給定限制和總價值儘可能大。

C++示例：

實施 ：

int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
    int dp[C+1];                               
    for (int i = 1; i <= C; ++i){
        dp[i] = -100000000;                   
    }
    dp[0] = 0;
    for (int i = 0; i < N; ++i){
        for (int j = C; j >= weight[i]; --j){
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[C];
}

測試 ：

3 5
5 2
2 1
3 2

輸出 ：

3

這意味著可以達到的最大值是 3，這可以通過選擇(2,1)和(3,2)來實現。

無界揹包

無界揹包問題是一個問題，它給出了一組專案，每個專案都有一個權重，一個值和無限的副本，確定要包含在一個集合中的每個專案的數量，以便總重量小於或等於給定的限制並且總價值儘可能大。

Python(2.7.11) 示例：

實施 ：

def unbounded_knapsack(w, v, c): # weight, value and capactiy
    m = [0]
    for r in range(1, c+1):
        val = m[r-1]
        for i, wi in enumerate(w):
            if wi > r:
                continue
            val = max(val, v[i] + m[r-wi])
        m.append(val)
    return m[c] # return the maximum value can be achieved

該實現的複雜性是 O(nC)，其中 n 是專案數。

測試 ：

w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]

print unbounded_knapsack(w, v, 13)

輸出 ：

20

這意味著可以達到的最大值是 20，這可以通過選擇(5,8)，(5,8)和(3,4)來實現。