Below the program will find the maximum value giving the following weight limit W. For example, having a W=5 (weight limit of 5), what is the maximum value?

Reference: repl.it example video

The answer should be 5+2+2 == 9. These are the values added up. The 5 has a weight of 3 and each 2 has a weight of 1 total weights = 3+1+1

def knapSack(W, wt, val):
# Simple Checks
if [i for i in wt if i <= 0] != []:
print("Weights must be < 0")
return False
if len(wt) != len(val) and len(val) >0 :
print("len(wt) != len(val) or len == 0")
return False
n = len(val)
K = [[0 for x in range(W+1)] for x in range(n+1)]
V = [[0 for x in range(W+1)] for x in range(n+1)]
# Build table K[][] in bottom up manner
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
if val[i-1] + K[i-1][w-wt[i-1]] > K[i-1][w]:
V[i][w]=val[i-1]
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
# Gets the items in our list
def minInList(target):
return min([ wt[j] for j in [o for o, x in enumerate(val) if x == target ]])
ans=[]
N = W
for i in range(-1,-(len(V)),-1):
if N > 0 and V[i][N] > 0:
ans.append(V[i][N])
N = N - minInList(V[i][N])
sum_weight=sum([minInList(i) for i in ans] )
return (K[n][W],sum_weight,ans)
# Driver program to test above function
val = [5,3,2,3,4,4]
wt = [3,2,1,1,1,1]
W = 7
print(knapSack(W, wt, val))
# This will return
# (18, 7, [4, 4, 3, 2, 5])
#
# Where 18 is the cumulative value
# 7 is the total weight actually obtained
# [4, 4, 3, 2, 5] Are the value items chosen
#
view raw EwNd-0.py hosted with ❤ by GitHub

Fractional weights

There’s another problem here, but it uses fractional weight. Note, you need to sort the values and weights, before calling the function.

# knapsack.py
# A dynamic programming algorithm for the 0-1 knapsack problem and
# a greedy algorithm for the fractional knapsack problem
# Modified from: http://personal.denison.edu/~havill/algorithmics/python/knapsack.py
# A dynamic programming algorithm for the 0-1 knapsack problem.
def Knapsack01(v, w, W):
n = len(v) - 1
c = [] # create an empty 2D array c
for i in range(n + 1): # c[i][j] = value of the optimal solution using
temp = [0] * (W + 1) # items 1 through i and maximum weight j
c.append(temp)
for i in range(1, n + 1):
for j in range(1, W + 1):
if w[i] <= j: # if item i will fit within weight j
if v[i] + c[i - 1][j - w[i]] > c[i - 1][j]: # add item i if value is better
c[i][j] = v[i] + c[i - 1][j - w[i]] # than without item i
else:
c[i][j] = c[i - 1][j] # otherwise, don't add item i
else:
c[i][j] = c[i - 1][j]
return c[n][W] # final value is in c[n][W]
# A greedy algorithm for the fractional knapsack problem.
# Note that we sort by v/w without modifying v or w so that we can
# output the indices of the actual items in the knapsack at the end
def KnapsackFrac(v, w, W):
order = bubblesortByRatio(v, w) # sort by v/w (see bubblesort below)
weight = 0.0 # current weight of the solution
value = 0.0 # current value of the solution
knapsack = [] # items in the knapsack - a list of (item, faction) pairs
n = len(v)
index = 0 # order[index] is the index in v and w of the item we're considering
while (weight < W) and (index < n):
if weight + w[order[index]] <= W: # if we can fit the entire order[index]-th item
knapsack.append((order[index], 1.0)) # add it and update weight and value
weight = weight + w[order[index]]
value = value + v[order[index]]
else:
fraction = (W - weight) / w[order[index]] # otherwise, calculate the fraction we can fit
knapsack.append((order[index], fraction)) # and add this fraction
weight = W
value = value + v[order[index]] * fraction
index = index + 1
return (knapsack, value) # return the items in the knapsack and their value
# sort in descending order by ratio of list1[i] to list2[i]
# but instead of rearranging list1 and list2, keep the order in
# a separate array
def bubblesortByRatio(list1, list2):
n = len(list1)
order = list(range(n))
for i in range(n - 1, 0, -1): # i ranges from n-1 down to 1
for j in range(0, i): # j ranges from 0 up to i-1
# if ratio of jth numbers > ratio of (j+1)st numbers then
if ((1.0 * list1[order[j]]) / list2[order[j]]) < ((1.0 * list1[order[j+1]]) / list2[order[j+1]]):
temp = order[j] # exchange "pointers" to these items
order[j] = order[j+1]
order[j+1] = temp
return order
v=[5.3,2,90]
w=[5.1,2,4.5]
W=9
v = [2,6,4,8,9,17.3,17,35,46]
w = [2,6,4,8,9,17,17,35,46]
W = 50
KnapsackFrac(v, w, W)
# Simple Examples above....
v = [2,6,4,8,9,17.3,17,35,46]
w = [2,6,4,8,9,17,17,35,46]
v = v + v
w = w + w
print(KnapsackFrac(v, w, W))
# Same value, but doesn't give you fraction. It finds the
# 4 and doesn't split the 8, like above.
v = [2,6,4,8,9,17.3,17,35,46]
w = [2,6,4,8,9,17,17,35,46]
v = v + v
w = w + w
v.sort()
w.sort()
print("\nNow, no split:")
print(KnapsackFrac(v, w, W))
view raw knapsackFrack.py hosted with ❤ by GitHub