0

我一直在研究背包问题的实现，但我无法正确实现它，代码只是不断进入这个 while(true)
的无限循环，这是代码：

class KSBB:
    global x
    global y
    x=[]
    y=[]
    global sp
    sp=0
    global cw
    global cp
    global nw
    global np
    cw,cp,nw,np=0,0,0,0
    global k
    k=0
    global pi
    pi=0
def __init__(self,a,b,c):
    self.weights=a
    self.values=b
    self.c=c
    x=len(self.weights)
    y=len(self.weights)

绑定方法：

def bound(self):
    global cp
    found=False
    bv=0
    n=len(self.weights)
    np=cp
    nw=cw
    pi=k
    while(pi < n and ~found):
        if(nw+self.weights[pi] <= self.c):
            nw+=self.weights[pi]
            np+=self.values[pi]
            y.append(1)
        else:
            bv=np+((self.c-nw)*(self.values[pi]/self.weights[pi]))
            found=True
            #y.append(0)
        pi+=1
    if found:
        pi-=1
        return bv
    else:
        return np

分支方法：

def Knapsack(self):
    n=len(self.weights)
    while True:
        global sp
        while (self.bound() <= sp):
            while(k !=0 and y[k] !=1):
                k-=1 
            if (K==0):return
            y[k]=0
            cw-=self.weights[k]
            cp-=self.values[k]
        cw=nw
        cp=np
        k=pi
        print k
        if (k==n):              
            sp=cp
            x=y
            k=n-1
        else:
            y[k]=0

输出方式：

def output(self):return sp
4

2 回答 2

3 
if (K==0)

应该是

if (k==0)

只是一个错字...

定位这个问题很容易——你知道你想在哪里终止你的循环，唯一可能出错的是你的if语句。发现这些东西很容易，也是编程中要掌握的最基本的东西之一。一旦你的程序开始超过 5 行，你就需要学习调试。

于 2013-07-01T23:36:57.397 回答
1

~found是按位补码。我想你的意思是not found！

>>> ~False
-1             # True
>>> ~True
-2             # also True!
于 2013-07-01T23:44:03.093 回答