0

现在我正在尝试在 Python 3.2 中编写背包问题。我试图用矩阵动态地做到这一点。我尝试使用的算法如下

实现背包问题的memoryfunction方法
输入：一个非负整数 i 表示第一个
正在考虑的物品和一个表示背包容量的非负整数 j
输出：前 i 项的最优可行子集的值
注意：用作全局变量输入数组 Weights[1..n], Values[1...n]
和表 V[0...n, 0...W]，其条目用 -1 初始化，除了
用 0 初始化的第 0 行和第 0 列

if V[i, j] < 0
    if j < Weights[i]
        value <-- MFKnapsack(i - 1, j)

    else
        value <-- max(MFKnapsack(i -1, j),
            Values[i] + MFKnapsack(i -1, j - Weights[i]))

    V[i, j} <-- value

return V[i, j]

如果您运行下面的代码，您可以看到它尝试将权重插入列表中。由于这是使用递归，我很难发现问题。我也收到错误消息：无法使用“+”将整数与列表相加。我将矩阵初始化为从第一行和第一列的所有 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()
4

3 回答 3

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

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

试试吧

F = [[-1]*capacityJ for _ in range(dimension)]

这是一个常见的 Python 陷阱。有关更多说明，请参阅此帖子。

于 2012-04-16T01:08:12.310 回答
0

出于缓存说明的目的，我一般使用默认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 中动态创建二维数组...

要使用这种方法查看 z1knapsack 的答案：

http://ideone.com/fUKZmq

于 2015-07-26T18:38:53.903 回答
0 
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()
于 2017-05-27T11:57:53.700 回答