背包问题

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)来实现。