fork download 
  1. from collections import defaultdict
  2. CS = defaultdict(lambda: defaultdict(int))
  3. def zeroOneKnapSack(numItems, sackSize, weights, values):
  4.  
  5.     if CS[numItems][sackSize] != 0:
  6.         return CS[numItems][sackSize]
  7.     if (numItems == 0) or (sackSize==0):
  8.         CS[numItems][sackSize] = 0
  9.         return 0
  10.     if weights[numItems] > sackSize:
  11.         CS[numItems][sackSize] = zeroOneKnapSack(numItems-1, sackSize, weights, values)
  12.         return CS[numItems][sackSize]
  13.  
  14.     CS[numItems][sackSize] = max( values[numItems]+zeroOneKnapSack(numItems-1, sackSize-weights[numItems], weights, values), 
  15.                                   zeroOneKnapSack(numItems-1, sackSize, weights, values) )
  16.  
  17.     return CS[numItems][sackSize]
  18.  
  19.  
  20. weights = [5,4,6,3]
  21. values = [10,40,30,50]
  22. sackSize = 10
  23. #another testcase
  24. # weights = [1,3,4,5]
  25. # values = [1,4,5,7]
  26. # sackSize = 7
  27. numItems = len(weights)-1 #could also use len(values)-1
  28. print zeroOneKnapSack(numItems, sackSize, weights, values)
Success #stdin #stdout 0.01s 7800KB
comments (?)
stdin 
Standard input is empty
stdout 
90
https://ideone.com/fUKZmq
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!