0-1带有负数的knapSnack问题

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]。获取这些数组取决于您的输入格式。