负数的 0-1 背包问题

Question

给定一个正数和负数数组，找出我们是否可以选择其中的一些并以最终总和为零的方式对它们求和。（任何非零数字都可以）。

我们有它们的权重和值。

我相信这是 0-1 背包问题的一个版本。示例输入和输出：

4 - weight - percent
+ 50 30
+ 80 1
- 20 30
- 30 30

yes

这是我为它编写的代码，但我不知道为什么它不起作用：我得到它的输出 0（我应该得到 1000，选择第一个、第三个和第四个）。有没有办法解决负值的背包问题？

def knapSack(W , wt , val , n): 
    if n == 0 : 
        return 0
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    else: 
        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1)) 

val = [80, 50, -20, -30] 
wt = [ 1,30, 30, 30] 
W = 0
n = len(val) 
print(knapSack(W, wt, val, n))

有人知道我应该如何更改它才能正常工作吗？

Answer 1

这绝不是有效的，但它似乎是查看酸和碱的任何组合是否会抵消的最简单方法。（我没有使用背包方式）

为每一种（酸和碱）创建一个包含它们数量的数组。在您的示例中，这些数组将是 - acid = [1500, 80] 和 base = [600, 900]。获取这些数组取决于您的输入格式。

获得这些数组后，您可以执行以下操作 -

def SumOfSubsets(arr): 
    Allsums = []
    for number in arr:
        Placeholder = Allsums[:]
        Allsums.append(number)
        for sum in Placeholder:
            Allsums.append(sum + number)

    return(Allsums)

AcidList = SumOfSubsets(acid)
BaseList = SumOfSubsets(base)

for acids in AcidList:
    if acids in BaseList:
        print("can be neutralized")

*请注意，通过使用这种方法，您不知道实现中和需要什么样的酸碱组合。如果需要，您可以通过使用另一个函数来获得此组合。

负数的 0-1 背包问题

0-1 knapSnack problem with negetive numbers

python

algorithm

knapsack-problem

graph-algorithm

data-structures