背包：从列表中添加项目（Python）

Question

我在写一个背包问题的代码。有一个有重量容量的背包，你选择一个特定的项目组合，以找到最好的解决方案。我试图随机生成可能的解决方案。因此，我的代码将选择随机数量的随机项（生成一个随机大小的列表），并测试解决方案是否可行（小于容量）或不可行（大于容量）。然而，当我试图把所有物品的总重量和总价值相加时，这个数字是关闭的。比如说，这是每一项的数据。

Itms    Wts     Vals   
=====================
1       22      80
2       29      35
3       12      36
4       14      24
5       29      41
6       30      87
7       18      10
8       22      63
9       12      66

10 27 72

Items picked:  [6, 4, 1, 7, 8, 3]
Feasible:  Total Wt =  18 Total Val =  10
Items picked:  [1]
Infeasible:  Total Wt =  135 Total Val =  264
Items picked:  [5, 1, 8, 6, 7, 4]
Infeasible:  Total Wt =  89 Total Val =  198

所以值是不正确的。但我看不出我的代码有什么问题：

def genSoln(cap,items):
    g = input("Would you like to generate random potential solutions? [y/n] ")
    if g == 'y':
        gen = int(input("Number of times to generate/check random potential solutions? "))
        totalwt = 0
        totalval = 0
        for i in range(1,gen+1):
            pop = range(1,items)
            leng = random.randint(1,len(pop))
            ran = random.sample(pop, leng)
            for i in ran:
                totalwt += int(wts[i])
                totalval += int(vals[i])
                if i == len(ran):
                    if totalwt < int(cap):
                        print("Items picked: ", ran)
                        print("Feasible: ", "Total Wt = ", totalwt, "Total Val = ", totalval)
                    else:
                        print("Items picked: ", ran)
                        print("Infeasible: ", "Total Wt = ", totalwt, "Total Val = ", totalval)
                    totalwt = 0
                    totalval = 0

Answer 1

不要紧。我自己想出了答案。我只需要取出，如果I==len(ran):，将totalwt和totalval移动到for循环中(for I在范围（1,gen+1))，并在添加到totalwt和totalval时从I中减去1。

def genSoln(cap,items):
    g = input("Would you like to generate random potential solutions? [y/n] ")
    if g == 'y':
        gen = int(input("Number of times to generate/check random potential solutions? "))
        for i in range(1,gen+1):
            totalwt = 0
            totalval = 0
            pop = range(1,items)
            leng = random.randint(1,len(pop))
            ran = random.sample(pop, leng)
            for i in ran:
                totalwt += int(wts[i-1])
                totalval += int(vals[i-1])
            if totalwt < int(cap):
                print("Items picked: ", ran)
                print("Feasible: ", "Total Wt = ", totalwt, "Total Val = ", totalval)
            else:
                print("Items picked: ", ran)
                print("Infeasible: ", "Total Wt = ", totalwt, "Total Val = ", totalval)