* NOT HOMEWORK *
I have implemented the knapsack in python and am successfully getting the best value however I would like to expand the problem to fill a table with all appropriate values for a knapsack table of all weights and items.
I've implemented it in python which I'm new to so please advise me if theres anything I could improve upon however the concepts should work in any language.
values, weights, table = [], [], [[]]
def knapsack(i, W):
global weights, values, table, counter
if (i < 0):
# Base case
return 0
if (weights[i] > W):
# Recursion
return knapsack(i - 1, W)
else:
# Recursion
return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
def main():
global values, weights, table
W = int(input())
values = list(map(int, input().split()))
weights = list(map(int, input().split()))
# initalise table with 0's
table = [[0 for i in range(W)] for i in range(len(values))]
for i in range(len(values)):
for j in range(W):
table[i][j] = 0
# Fill table
print("Result: {}".format(knapsack(len(values) - 1, W)))
printKnapsack(W)
if __name__ == '__main__':
main()
I also have this print table method which is unrelated but just so you can see what I'm outputting it as:
def printLine(W):
print(" ",end="")
for i in range(W + 1):
print("-----",end="")
print("")
def printKnapsack(W):
global table
print("\nKnapsack Table:")
printLine(W)
print("| k\w |", end="")
for i in range(W):
print("{0: >3} |".format(i + 1), end="")
print("")
printLine(W)
for i in range(len(values)):
print("| {} |".format(i+1), end="")
for j in range(W):
print("{0: >3} |".format(table[i][j]), end="")
print("")
printLine(W)
This is the sample input:
10
18 9 12 25
5 2 4 6
This is what is should output:
Result: 37
Knapsack Table:
-------------------------------------------------------
| k\w | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
-------------------------------------------------------
| 1 | 0 | 0 | 0 | 0 | 18 | 18 | 18 | 18 | 18 | 18 |
-------------------------------------------------------
| 2 | 0 | 9 | 9 | 9 | 18 | 18 | 27 | 27 | 27 | 27 |
-------------------------------------------------------
| 3 | 0 | 9 | 9 | 12 | 18 | 21 | 27 | 27 | 30 | 30 |
-------------------------------------------------------
| 4 | 0 | 9 | 9 | 12 | 18 | 25 | 27 | 34 | 34 | 37 |
-------------------------------------------------------
I have tried multiple different lines in the knapsack(i, W) function to add elements to the table and I've drawn it out but I can't understand how the recursion is working well enough to figure out what indexes to put in to add the unravelled recursive call values to.
This is the method I have to fix.
def knapsack(i, W):
global weights, values, table, counter
if (i < 0):
# Base case
return 0
if (weights[i] > W):
# Recursion
table[?][?] = ?
return knapsack(i - 1, W)
else:
# Recursion
table[?][?] = ?
return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
In your recursive algorithm you just can't get full filled table, because this step skip a lot:
return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
I can sudgest you this solution:
def knapsack(i, W):
global weights, values, table, counter
if (i < 0):
# Base case
return 0
if (weights[i] > W):
# Recursion
table[i][W-1] = knapsack(i - 1, W)
else:
# Recursion
table[i][W-1] = max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
return table[i][W-1]
In resulted table non-zero cells means that your algorithm step through here and got this intermediate solution. Also you can run your algorithm more than once with different input values and got full-filled table.
Hope this helped