背包任务中所有组合的数量

Question

有经典Knapsack problem。我对这个问题的看法有点不同。

给定一组物品，每个物品都有质量，确定包装物品的组合数量，使总重量小于或等于给定限制。

例如，有 5 件商品质量为：1, 1, 3, 4, 5。 limit = 7 存在错误。有以下组合：

有没有不用暴力计算组合数的方法？

Answer 1

每件物品使用次数不限

这很简单原始问题的扩展。

您可能知道您使用 DP 来解决原始问题，其中项目的重量必须正好是 W。当您使用 DP 完成时，您还将获得所有重量 < W 的解决方案。得到您的解决方案 简单地总结 权重从 1 到 W 的解决方案（对于空集 +1）。

每个项目使用一次

在这种情况下，没有别的办法，只能暴力破解所有可能的组合。这个问题是 NP 难的，时间复杂度为 O(2^n)。

暴力破解使用下一个代码（借自@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)

Answer 2

这是一个解决方案：

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]

Answer 3

以及其他人也发布了一些解决方案，这里是使用 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

测试-运行

λ> 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],[]]

发生了什么事？

从 5 开始，您有两个选择：要么接受，要么不接受。

如果你接受它，你还剩 2 个限制，所以你应该递归地寻找有多少种方法可以做到这一点
如果不是你仍然有限制 7 但只有 1,1,3,4 寻找....

该算法以一种充满希望的可读方式将其转换为基本 Haskell - 请随时询问详细信息

备注

我根本没有看性能 - 但做与处理原始问题相同的事情应该很容易（重写 table 的列，...）

背包任务中所有组合的数量

Number of all combinations in Knapsack task

algorithm

combinations

dynamic-programming

测试-运行

发生了什么事？

备注