英文:
0-1 knapSnack problem with negetive numbers
问题
以下是您要翻译的部分:
"Given an array of positive and negative numbers, find if we can choose some of them and sum them in a way that the final sum is zero. (any non zero number will do).
We have weights of them and values.
I believe this is a version of the 0-1 knapsack problem.
the sample input and output:
4 - weight - percent
+ 50 30
+ 80 1
- 20 30
- 30 30
yes
This is the code I wrote for it, but somehow I can't figure out why this won't work:
I'm getting the output 0 for it (and I should be getting 1000, choosing the first, third and fourth one).
Is there any way to solve the knapsack problem with negative values?
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))
Anyone has any idea how should I change this in order to be working?"
英文:
Given an array of positive and negative numbers, find if we can choose some of them and sum them in a way that the final sum is zero. (any non zero number will do).
We have weights of them and values.
I believe this is a version of the 0-1 knapsack problem.
the sample input and output:
4 - weight - percent
+ 50 30
+ 80 1
- 20 30
- 30 30
yes
This is the code I wrote for it, but somehow I can't figure out why this won't work:
I'm getting the output 0 for it (and I should be getting 1000, choosing the first, third and fourth one).
Is there any way to solve the knapsack problem with negative values?
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))
Anyone has any idea how should I change this in order to be working??
答案1
得分: 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("可以中和")
*请注意,使用这种方法,你无法知道需要哪些酸和碱的组合来实现中和。如果需要,你可以使用另一个函数来获取这个组合。
英文:
This is by no ways efficient but it seemed to be the simplest method of seeing if any combination of acids and bases would cancel out. (I did not use the knapsack approach)
For each (the acids and the bases) create an array that contains their amount. In the case of your example these arrays would be - acid = [1500, 80]
and base = [600, 900]
. Getting these arrays depends on your input format.
once you have these arrays you can do the following -
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")
*Note that by using this approach you do not know what combinations of acids and bases are needed to achieve the neutralization. You can get this combination by using another function if needed.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论