Python动态Knaps

Question

现在我正试图用Python3.2编写背包问题的代码。我试着用矩阵来动态地做这个。我尝试使用的算法如下

Implements the memoryfunction method for the knapsack problem 
Input: A nonnegative integer i indicating the number of the first
items being considered and a nonnegative integer j indicating the knapsack's capacity
Output: The value of an optimal feasible subset of the first i items
Note: Uses as global variables input arrays Weights[1..n], Values[1...n]
and table V[0...n, 0...W] whose entries are initialized with -1's except for
row 0 and column 0 initialized with 0's

^{pr2}$

如果你运行下面的代码，你可以看到它试图将权重插入到列表中。由于这是使用递归，我很难发现问题。我还得到了一个错误：不能用'+'添加一个带有列表的整数。我已经将矩阵初始化为从第一行和第一列的所有0开始，其他所有的都初始化为-1。任何帮助都将不胜感激。在

#Knapsack Problem 


def knapsack(weight,value,capacity):
    weight.insert(0,0)
    value.insert(0,0)

    print("Weights: ",weight)
    print("Values: ",value)

    capacityJ = capacity+1

    ## ------ initialize matrix F ---- ##
    dimension = len(weight)+1
    F = [[-1]*capacityJ]*dimension

    #first column zeroed
    for i in range(dimension):
        F[i][0] = 0
    #first row zeroed            
    F[0] = [0]*capacityJ
    #-------------------------------- ##

    d_index = dimension-2
    print(matrixFormat(F))

    return recKnap(F,weight,value,d_index,capacity)

def recKnap(matrix, weight,value,index, capacity):

    print("index:",index,"capacity:",capacity)
    if matrix[index][capacity] < 0:
        if capacity < weight[index]:
            value = recKnap(matrix,weight,value,index-1,capacity)
        else:
            value = max(recKnap(matrix,weight,value,index-1,capacity),
                        value[index] +
                        recKnap(matrix,weight,value,index-1,capacity-(weight[index]))

    matrix[index][capacity] = value
    print("matrix:",matrix)


    return matrix[index][capacity]


def matrixFormat(*doubleLst):
    matrix = str(list(doubleLst)[0])
    length = len(matrix)-1
    temp = '|'
    currChar = ''
    nextChar = ''
    i = 0

    while i < length:
        if matrix[i] == ']':
            temp = temp + '|\n|'
        #double digit
        elif matrix[i].isdigit() and matrix[i+1].isdigit():
            temp = temp + (matrix[i]+matrix[i+1]).center(4)
            i = i+2
            continue
        #negative double digit
        elif matrix[i] == '-' and matrix[i+1].isdigit() and matrix[i+2].isdigit():
            temp = temp + (matrix[i]+matrix[i+1]+matrix[i+2]).center(4)
            i = i + 2
            continue
        #negative single digit
        elif matrix[i] == '-' and matrix[i+1].isdigit():
            temp = temp + (matrix[i]+matrix[i+1]).center(4)
            i = i + 2
            continue




        elif matrix[i].isdigit():
            temp = temp + matrix[i].center(4)

        #updates next round
        currChar = matrix[i]
        nextChar = matrix[i+1]
        i = i + 1

    return temp[:-1]




def main():
    print("Knapsack Program")
    #num = input("Enter the weights you have for objects you would like to have:")
    #weightlst = []
    #valuelst = []
##    for i in range(int(num)):
##        value , weight = eval(input("What is the " + str(i) + " object value, weight you wish to put in the knapsack?  ex. 2,3: "))
##        weightlst.append(weight)
##        valuelst.append(value)
    weightLst = [2,1,3,2]
    valueLst = [12,10,20,15]
    capacity = 5

    value = knapsack(weightLst,valueLst,5)

    print("\n      Max Matrix")
    print(matrixFormat(value))

main()

Answer 1

为了说明缓存，我通常使用默认dict，如下所示：

from collections import defaultdict
CS = defaultdict(lambda: defaultdict(int)) #if i want to make default vals as  0
###or
CACHE_1 = defaultdict(lambda: defaultdict(lambda: int(-1))) #if i want to make default vals as -1 (or something else)

这让我无法在运行中用python制作2d数组。。。在

要使用此方法查看Z1背包的答案：

http://ideone.com/fUKZmq

Answer 2

F = [[-1]*capacityJ]*dimension

无法正确初始化矩阵。[-1]*capacityJ很好，但是[...]*dimension会创建dimension对完全相同的列表的引用。因此，修改一个列表将修改所有列表。在

试试吧

^{2}$

这是一个常见的Python陷阱。有关详细说明，请参见this post。在

Answer 3

def zeroes(n,m):
    v=[['-' for i in range(0,n)]for j in range(0,m)]
    return v
value=[0,12,10,20,15]
w=[0,2,1,3,2]
v=zeroes(6,5)

def knap(i,j):
    global v
    if i==0 or j==0:
        v[i][j]= 0
    elif j<w[i] :
        v[i][j]=knap(i-1,j)
    else:
        v[i][j]=max(knap(i-1,j),value[i]+knap(i-1,j-w[i]))
    return v[i][j]
x=knap(4,5)
print (x)
for i in range (0,len(v)):
    for j in range(0,len(v[0])):
        print(v[i][j],end="\t\t")
    print()
print()
#now these calls are for filling all the boxes in the matrix as in the above call only few v[i][j]were called and returned
knap(4,1)
knap(4,2)
knap(4,3)
knap(4,4)               

for i in range (0,len(v)):
    for j in range(0,len(v[0])):
        print(v[i][j],end="\t\t")
    print()
print()