蛮力背包打印输出

Question

我正在使用组合来显示背包中所有可能的物品总子集，所以如果我有 10 件物品，具有不同的价值和重量，它会显示物品的所有组合，总重量是在元组 (Id、Weight、Val) 和总值的第二个位置，我的问题是我得到一个元组索引超出范围的错误。

#Knapsack

from random import *
from itertools import *

#Creates List of Items, using N for Num of Items
#Weightmax for the max range of weights
#Valmax of max value range
#Each Item has a Id, Weight and Value.
#Represented as a tuple. [(Id,Weight,Value)]
def item_list(n,weightmax,valmax):

    items = []
    for i in range(1,n+1):
        items.append((i,randrange(1,weightmax),randrange(1,valmax)))
    return items
#----------------------------------------------------
#Is the Sack, Takes Items as a parameter, and Capacity
#Purpose is to find and print all possible combinations that
#Will fit in the sack,then print which subset has the best
#weight for value mix.
def knapsack(items,capacity):
    sack = items
    subs = []
    print("------------------------------")
    print("Subset,","     |      ", "Total Weight", "     |     ", "Total Value")
    for i in range(len(sack)+1):
        print(i)
        for j in combinations(items, i):
            subs.append(j)
            print(j,"   |   ",j[i][1],"   |   ",j[i][2])

#------------------------------------    
#Main, Asks for UserInput and allows you
#to re-enter mistypes.
def main():
    choices = False 
    print("Welcome to the Knapsack Filler!")
    print("Please Input the Following Parameters; ")
    while choices is False:
        knapcap = int(input("Enter Knapsack Max Capacity: "))
        maxweight = int(input("Enter Max Range for Weights: "))
        maxval = int(input("Enter Max Value Range for Weights: "))
        numitems = int(input("Number of Items you wish to generate: "))
        prompt= input("\n Y or N; Are you Sure about your Choices?: ")
        if prompt.lower() =="yes" or "y":
            choices = True
        else:
            pass
    knapsack(item_list(numitems,maxweight,maxval),knapcap)
main()

错误：

Traceback (most recent call last):
  File "C:\CS230\CS320_P2_Knapsack.py", line 54, in <module>
    main()
  File "C:\CS230\CS320_P2_Knapsack.py", line 53, in main
    knapsack(item_list(numitems,maxweight,maxval),knapcap)
  File "C:\CS230\CS320_P2_Knapsack.py", line 31, in knapsack
    print(j,"   |   ",j[i][1],"   |   ",j[i][2])
IndexError: tuple index out of range

示例输入：

Welcome to the Knapsack Filler!
Please Input the Following Parameters; 
Enter Knapsack Max Capacity: **30**
Enter Max Range for Weights: **10**
Enter Max Value Range for Weights: **10**
Number of Items you wish to generate: **3**

 Y or N; Are you Sure about your Choices?: Y
------------------------------
Subset,      |       Total Weight      |      Total Value
0

Answer 1

这是一个很难回答的问题，因为您遇到的问题来自代码中的概念和架构困难。我已经以类似于我自己完成的方式重写了您的代码，希望看到 "good code" 可以帮助您找出可能哪里出错了。

我所做的一些主要更改包括：

引入幂集函数，因为这是您要生成的项目列表
引入 Item class 使 id、weight 和 value 清晰可见
引入 Sack class 来抽象查找项目重量和价值子集的细节

如果您还不知道如何使用 classes，了解它们确实是件好事，如下面的代码所示。

代码

#!/usr/bin/env python3

import random
import itertools

class Item:
  def __init__(self, id, weight, value):
    self.id     = id
    self.weight = weight
    self.value  = value

class Sack:
  def __init__(self, items):
    self.items = items

  def weight(self):
    return sum([x.weight for x in self.items])

  def value(self):
    return sum([x.value for x in self.items])

  def ids(self):
    return ', '.join([str(x.id) for x in self.items])

  def __repr__(self): #What gets shown when you call the print function
    return "{0:10} {1:10}   {2}".format(self.weight(), self.value(), self.ids())


def powerset(iterable):
  """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)

    Source: https://docs.python.org/2/library/itertools.html
  """
  s = list(iterable)
  return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))



def item_list(n,weightmax,valmax):
  """
    Creates a list of randomly generated items

    Arguments:
      n          Number of items to have in the sack
      weightmax  Weights are generated in the range [1,weightmax]
      valuemax   Values are generated in the range [1,valuemax]

    Returns:
      A list of [(Id,Weight,Value), (Id,Weight,Value), ...]
"""
  items = []
  for i in range(1,n+1):
    items.append(Item(id=i, weight=random.randint(1,weightmax), value=random.randint(1,valmax)))
  return items



def knapsack(items,capacity):
  """Find and print all the combinations of items that will fit into the sack.
     Also print the most valuable combination.

    Arguments:
      items      A list of items generated by item_list()
      capacity   The maximum weight the knapsack can hold
  """
  print("------------------------------")
  print("{0:>10} {1:>10}   {2}".format("Weight","Value","Subset"))
  subsets_that_fit = []
  for sackitems in powerset(items):
    sack = Sack(sackitems)
    if sack.weight()>capacity:
      continue
    print(sack)
    subsets_that_fit.append(sack)
  best = max(subsets_that_fit, key=lambda x: x.value())
  print("Best")
  print(best)



def main():
  choices = False 
  print("Welcome to the Knapsack Filler!")
  print("Please Input the Following Parameters; ")
  while choices is False:
    knapcap   = int(input("Enter Knapsack Max Capacity: "))
    maxweight = int(input("Enter Max Range for Weights: "))
    maxval    = int(input("Enter Max Value Range for Weights: "))
    numitems  = int(input("Number of Items you wish to generate: "))
    prompt    = input("\n Y or N; Are you Sure about your Choices?: ")
    if prompt.lower() =="yes" or "y":
      choices = True
    else:
      pass

  knapsack(item_list(numitems,maxweight,maxval),knapcap)

main()

蛮力背包打印输出

Brute-Force Knapsack Printout

python

algorithm

combinations

knapsack-problem

mathematical-optimization