0-1背包问题中的负数情况

huangapple go评论88阅读模式
英文:

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.

huangapple
  • 本文由 发表于 2020年1月3日 17:46:38
  • 转载请务必保留本文链接:https://go.coder-hub.com/59576274.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定