找到你要的答案

Q:Number of all combinations in Knapsack task

Q:背包任务中的所有组合数

There is a classic Knapsack problem. My version of this problem is a little different.

Given set of items, each with a mass, determine the number of combinations to pack items so that the total weight is less than or equal to a given limit.

For example, there is 5 items with mass: 1, 1, 3, 4, 5. There is a bug with limit = 7. There are the following combinations:

1 + 3
1 + 4
1 + 5
1 + 1 + 3
1 + 1 + 4
1 + 1 + 5
3
3 + 4
4
5

Is there a way to count number of combinations without brute?

有一个经典背包问题。我版本的这个问题有点不同。

给定的一组项,每一个有一个质量,确定组合的数量来包装项目,使总重量小于或等于一个给定的限制。

例如,有5个项目与质量:1,1,3,4,5。有一个错误的限制= 7。有以下组合:

1 + 3
1 + 4
1 + 5
1 + 1 + 3
1 + 1 + 4
1 + 1 + 5
3
3 + 4
4
5

有没有一种方法来计算没有野兽的组合数?

answer1: 回答1:

This is one solution:

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

prints:

[]
[5]
[4]
[3]
[3, 4]
[1]
[1, 5]
[1, 4]
[1, 3]
[1]
[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]

这是一个解决方案:

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

版画:

[]
[5]
[4]
[3]
[3, 4]
[1]
[1, 5]
[1, 4]
[1, 3]
[1]
[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]
answer2: 回答2:

well as others posted some solutions too, here is a translation of the naive extension of the problem using Haskell and simple recursion:

combinations :: Int -> [Int] -> [[Int]]
combinations _ [] = [[]]
combinations w (x:xs)
  | w >= x = [ x:ys | ys <- combinations (w-x) xs] ++ combinations w xs
  | otherwise = combinations w xs

test-run

λ> combinations 7 [5,4,3,1,1]
[[5,1,1],[5,1],[5,1],[5],[4,3],[4,1,1],[4,1],[4,1],[4],[3,1,1],[3,1],[3,1],[3],[1,1],[1],[1],[]]

what's going on?

starting with 5 you have two choices: either you take it or not.

  • if you take it you have limit 2 left and so you should recursively look for how many ways you can do this
  • if not you still have limit 7 but only 1,1,3,4 to look for ....

the algorithm translates this into basic Haskell in a hopeful readable way - feel free to ask for details

remarks

I did not look at the performance at all - but it should be easy doing the same stuff you would do with the original problem (rewrite columns of the table, ...)

以及其他一些解决方案的发布,这是一个翻译使用Haskell和简单的递归问题的天真的延伸:

combinations :: Int -> [Int] -> [[Int]]
combinations _ [] = [[]]
combinations w (x:xs)
  | w >= x = [ x:ys | ys <- combinations (w-x) xs] ++ combinations w xs
  | otherwise = combinations w xs

test-run

λ> combinations 7 [5,4,3,1,1]
[[5,1,1],[5,1],[5,1],[5],[4,3],[4,1,1],[4,1],[4,1],[4],[3,1,1],[3,1],[3,1],[3],[1,1],[1],[1],[]]

what's going on?

从5开始你有两个选择:要么你拿,要么没有。

  • if you take it you have limit 2 left and so you should recursively look for how many ways you can do this
  • if not you still have limit 7 but only 1,1,3,4 to look for ....

该算法转化为一个充满希望的可读的方式基本Haskell随时问细节

remarks

我没有看性能-但它应该很容易做同样的东西,你会做原来的问题(重写表的列,…)

answer3: 回答3:

EACH ITEM USED UNLIMITED TIMES

This is rather straightforward extension of original problem.

As you probably know you use DP to solve original problem, where weight of items must be exactly W. When you finish with DP, you will also have solution for all weights < W. To get your solution simply sum up solutions for weights from 1 to W (and +1 for empty set).

EACH ITEM USED ONCE

In this case, there is not other way, but to brute-force all possible combinations. This problem is NP-hard and will have time complexity of O(2^n).

To brute-force use next code (borrowed from @pjsofts):

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)

每个项目使用无限次

这是原始问题的直接扩展。

你可能知道你用DP解决原来的问题,那里的物品重量必须是W。当你完成了DP,你也会有解决方案的所有重量<;W得到您的解决方案简单总结解决方案的权重从1 W(+ 1为空集)。

每项使用一次

在这种情况下,没有其他的方式,而是蛮力所有可能的组合。这个问题是NP-难的,将有时间复杂度为O(2。

蛮力用下代码(来自@ pjsofts借来的):

items = [1,1,3,4,5]
knapsack = []
limit = 7

def print_solutions(current_item, knapsack, current_sum):
    #if all items have been processed print the solution and return:
    if current_item == len(items):
        print knapsack
        return

    #don't take the current item and go check others
    print_solutions(current_item + 1, list(knapsack), current_sum)

    #take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit):
        knapsack.append(items[current_item])
        current_sum += items[current_item]
        #current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum )

print_solutions(0,knapsack,0)
algorithm  combinations  dynamic-programming