Brute-Force Knapsack Printout
An answer to this question on Stack Overflow.
Question
I"m using combinations to show all total subsets of items possible within a knapsack, So if I had like 10 items, with varying value and weight It'd show all combinations of the items, the total weights which is in the second spot in the tuple (Id,Weight,Val) and the total values, my issue is I'm getting a tuple index out of range error.
#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()
Error:
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
Sample Input:
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
This is a difficult question to answer because the problem you're having arises from conceptual, but also architectural difficulties in your code. I've rewritten your code in a form similar to how I would have done it myself in the hopes that seeing "good code" will help you figure out where you may have gone wrong.
A few of the major changes I've made include:
- Introducing a powerset function, since this is the list of items you're trying to generate
- Introducing an
Itemclass to make id, weight, and value clearly accessible - Introducing a
Sackclass to abstract the details of finding a subset of items' weight and value
If you don't know how to use classes yet, they're really good things to know, as the code below demonstrates.
Code
#!/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()