knapsack multiple constraints

I have a dynamic programming question which I have spent hours researching to no avail.

The first part is easy: you have a knapsack of items, and you have to maximise the value of these items, whilst keeping them below a certain weight.

The second part of the question is the same, except now there is also an item limit. so for example:

What is the max value of items you could put in the bag such that value is maximised with both weight and item limit?

I have no idea how to implement the second part of this question, Im looking for a general algorithm.

---

In the dynamic programming solution without item limit you have 2D matrix where Y-axis is item index and X-axis is weight. Then for each item, weight pair you choose maximum between

value of weight including item if item weight <= weight limit

value of weight excluding item

Here's example of the standard solution in Python:

def knapsack(n, weight, values, weights):
    dp = [[0] * (weight + 1) for _ in range(n + 1)]

    for y in range(1, n + 1):
        for x in range(weight + 1):
            if weights[y - 1] <= x:
                dp[y][x] = max(dp[y - 1][x],
                               dp[y - 1][x - weights[y - 1]] + values[y - 1])
            else:
                dp[y][x] = dp[y - 1][x]

    return dp[-1][-1]

Now when you add the item limit you have to choose maximum value for each item, value, number of items used triplet from

value of weight and n items including item if item weight <= weight limit

value of weight and n items excluding item

In order to represent number of items you can just add third dimension to the previously used matrix that represents the number of used items:

def knapsack2(n, weight, count, values, weights):
    dp = [[[0] * (weight + 1) for _ in range(n + 1)] for _ in range(count + 1)]
    for z in range(1, count + 1):
        for y in range(1, n + 1):
            for x in range(weight + 1):
                if weights[y - 1] <= x:
                    dp[z][y][x] = max(dp[z][y - 1][x],
                                      dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1])
                else:
                    dp[z][y][x] = dp[z][y - 1][x]

    return dp[-1][-1][-1]

Simple demo:

w = 5
k = 2
values = [1, 2, 3, 2, 2]
weights = [4, 5, 1, 1, 1]
n = len(values)

no_limit_fmt = 'Max value for weight limit {}, no item limit: {}'
limit_fmt = 'Max value for weight limit {}, item limit {}: {}'

print(no_limit_fmt.format(w, knapsack(n, w, values, weights)))
print(limit_fmt.format(w, k, knapsack2(n, w, k, values, weights)))

Output:

Max value for weight limit 5, no item limit: 7
Max value for weight limit 5, item limit 2: 5

Note that you could optimize the example a bit regarding memory consumption since when adding zth item to the solution you only need to know the solution for z - 1 items. Also you could check if it's is possible to fit z items under the weight limit to begin with and if not reduce the item limit accordingly.

链接地址: http://www.djcxy.com/p/59948.html

上一篇: 使用cakephp将amazon s3帐户中的文件下载到另一个s3帐户

下一篇: 背包多重约束