0-1+knapsacknmnbbhhjhvhjhj-hjkbbjbj.pptx

hj

1. Time complexity:   Space complexity:   4 5 1 7 2 6 3 8 a Space complexity:     text text no margin no margin text text no margin no margin rec(n)   5 5 [ 4 , 5 , 1 , 7 , 2 , 6 , 3 , 8 ] left no margin mid no margin $ no margin no margin no margin no margin 5 5 "string" list list list list      

2. 0-1 knapsack

3. 6 kg 20 $ 5 kg 15 $ 13 kg 30 $ 10 kg 25 $ 3 kg 10 $

4. 6 kg 20 $ 5 kg 15 $ 13 kg 30 $ 10 kg 25 $ 3 kg 10 $ Capacity: 20kg

5. We have items, each one of them has a value and a weight , and we want to determine which items to take without exceeding the maximum weight while having a total value that is as big as possible, you are asked to return their total value.    

6. We have items, each one of them has a value and a weight , and we want to determine which items to take without exceeding the maximum weight while having a total value that is as big as possible, you are asked to return their total value.       maximize subject to  

7. 6 kg 20 $ 5 kg 15 $ 13 kg 30 $ 10 kg 25 $ 3 kg 10 $ Capacity: 20kg input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 output: 55 explanation: we take items 0, 3, and 4  

8. 6 kg 20 $ 5 kg 15 $ 13 kg 30 $ 10 kg 25 $ 3 kg 10 $ Capacity: 20kg input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 output: 55 explanation: we take items 0, 3, and 4  

9. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 knapsack ( 20 , ) k i

10. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 knapsack ( 20 , ) k i knapsack ( 14 , 1 ) knapsack ( 20 , 1 )    

11. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 knapsack ( 20 , ) k i knapsack ( 14 , 1 ) knapsack ( 1 , 2 ) knapsack ( 14 , 2 ) knapsack ( 7 , 2 ) knapsack ( 20 , 2 ) knapsack ( 20 , 1 )            

16.               def knapsack ( values , weights , k , i = ) : if i == len ( values ) : return elif weights [ i ] > k : return knapsack ( values , weights , k , i + 1 ) else : return max ( values [ i ] + knapsack ( values , weights , k - weights [ i ], i + 1 ), knapsack ( values , weights , k , i + 1 ))

17.               def knapsack ( values , weights , k , i = ) : if i == len ( values ) : return elif weights [ i ] > k : return knapsack ( values , weights , k , i + 1 ) else : return max ( values [ i ] + knapsack ( values , weights , k - weights [ i ], i + 1 ), knapsack ( values , weights , k , i + 1 ))

18. def knapsack ( values , weights , k , i = ) : if i == len ( values ) : return elif weights [ i ] > k : return knapsack ( values , weights , k , i + 1 ) else : return max ( values [ i ] + knapsack ( values , weights , k - weights [ i ], i + 1 ), knapsack ( values , weights , k , i + 1 )) knapsack ( k , ) knapsack ( k , 1 ) knapsack ( k , n ) . . .

19. def knapsack ( values , weights , k , i = ) : if i == len ( values ) : return elif weights [ i ] > k : return knapsack ( values , weights , k , i + 1 ) else : return max ( values [ i ] + knapsack ( values , weights , k - weights [ i ], i + 1 ), knapsack ( values , weights , k , i + 1 )) knapsack ( k , ) knapsack ( k , 1 ) knapsack ( k , n ) . . .  

20.   knapsack(k,0) knapsack(k,1) knapsack(k,n) . . .  

21. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 7 , 10 , 3 ] k = 20 k ( 17 , 5 ) k ( 14 , 5 ) k ( 11 , 5 ) k ( 10 , 5 ) k ( 7 , 5 ) k ( 4 , 5 ) k ( 3 , 5 ) k ( 1 , 5 ) k ( , 5 ) k ( 20 , 5 ) k ( 20 , 2 ) k ( 20 , 3 ) k ( 7 , 2 ) k ( 1 , 2 ) k ( 14 , 2 ) k ( 7 , 3 ) k ( 1 , 3 ) k ( 14 , 3 ) k ( 20 , 1 ) k ( 14 , 1 ) k ( 20 , ) k ( 20 , 4 ) k ( 7 , 4 ) k ( 1 , 4 ) k ( 14 , 4 ) k ( 13 , 3 ) k ( , 3 ) k ( 10 , 4 ) k ( 4 , 4 ) k ( 3 , 4 ) k ( , 4 ) k ( 13 , 4 ) k ( 13 , 3 )

22. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 7 , 10 , 3 ] k = 20 k ( 17 , 5 ) k ( 14 , 5 ) k ( 11 , 5 ) k ( 10 , 5 ) k ( 7 , 5 ) k ( 4 , 5 ) k ( 3 , 5 ) k ( 1 , 5 ) k ( , 5 ) k ( 20 , 5 ) k ( 20 , 2 ) k ( 20 , 3 ) k (7,2) k ( 1 , 2 ) k (14,2) k (7,3) k ( 1 , 3 ) k ( 14 , 3 ) k ( 20 , 1 ) k ( 14 , 1 ) k ( 20 , ) k ( 20 , 4 ) k ( 7 , 4 ) k ( 1 , 4 ) k ( 14 , 4 ) k ( 13 , 3 ) k ( , 3 ) k ( 10 , 4 ) k ( 4 , 4 ) k ( 3 , 4 ) k ( , 4 ) k ( 13 , 4 ) k ( 13 , 3 )

23. def knapsack ( values , weights , k , i = , lookup = None ) : lookup = {} if lookup is None else lookup if ( k , i ) in lookup : return lookup [( k , i )] elif i == len ( values ) : return elif weights [ i ] > k : lookup [( k , i )] = knapsack ( values , weights , k , i + 1 , lookup ) return lookup [( k , i )] else : lookup [( k , i )] = max ( values [ i ] + knapsack ( values , weights , k - weights [ i ], i + 1 , lookup ), knapsack ( values , weights , k , i + 1 , lookup )) return lookup [( k , i )] 1 2 3 4

26.   call stack size lookup table size

28. dp[ n-1 ][ k ] represents the maximum value that we can get from the array of items that ends at the item n-1 , the last one, with a maximum weight of k

29. dp[ i ][ j ] represents the maximum value that we can get from the array of items that ends at the item i , the last one, with a maximum weight of j

30. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

31. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

32. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

33. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

34. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

35. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

36. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

37. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

38. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

39. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

40. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

41. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 When we can take the item , to get the value of , we check if it's better to take the item and subtract its weight or to not take it at all  

42. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

43. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

44. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

45. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

46. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

47. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

48. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

49. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

50. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

51. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

52. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

53. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

54. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

55. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

56. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

57. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

58. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

59. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

60. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

61. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

62. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

63. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

64. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

65. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

66. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

67. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

68. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

69. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

70. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

71. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

72. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

73. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

74. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

75. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

76. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

77. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

78. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

79. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

80. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

81. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

82. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

83. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

84. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

85. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

86. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

87. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

88. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

89. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

90. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

91. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

92. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

93. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

94. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

95. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

96. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

97. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

98. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

99. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

100. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

101. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

102. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

103. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

104. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

105. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

106. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

107. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

108. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

109. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

110. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

111. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

112. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

113. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

114. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

115. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

116. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

117. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

118. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

119. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

120. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

121. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

122. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 55 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

123. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 55 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

124. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 55 55 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20     input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20

125. input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 5 , 10 , 3 ] k = 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 15 20 20 20 20 20 35 35 35 35 35 35 35 45 50 50 15 20 20 20 20 25 35 35 35 35 40 45 45 45 50 50 10 10 15 20 20 25 30 30 35 35 35 45 45 45 45 50 55 55 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    

126. def knapsack ( values , weights , k ) : if k == 0: return 0 elif k >= sum(weights): return sum(values) n = len(values) dp = [[0]*(k+1) for i in range(n)] for i in range(weights[0], k+1): dp[0][i] = values[0] for i in range(1, n): for j in range(k+1): if weights[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(values[i]+dp[i-1][j-weights[i]], dp[i-1][j]) return dp[n-1][k]

127. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len(values) dp = [[0]*(k+1) for i in range(n)] for i in range(weights[0], k+1): dp[0][i] = values[0] for i in range(1, n): for j in range(k+1): if weights[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(values[i]+dp[i-1][j-weights[i]], dp[i-1][j]) return dp[n-1][k]

128. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range(weights[0], k+1): dp[0][i] = values[0] for i in range(1, n): for j in range(k+1): if weights[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(values[i]+dp[i-1][j-weights[i]], dp[i-1][j]) return dp[n-1][k]

129. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range ( weights [ ], k + 1 ) : dp [ ][ i ] = values [ ] for i in range(1, n): for j in range(k+1): if weights[i] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(values[i]+dp[i-1][j-weights[i]], dp[i-1][j]) return dp[n-1][k]

130. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range ( weights [ ], k + 1 ) : dp [ ][ i ] = values [ ] for i in range ( 1 , n ) : for j in range ( k + 1 ) : if weights [ i ] > j : dp [ i ][ j ] = dp [ i - 1 ][ j ] else : dp [ i ][ j ] = max ( v alues [ i ] + dp [ i - 1 ][ j - weights [ i ]], dp [ i - 1 ][ j ]) return dp[n-1][k]

131. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range ( weights [ ], k + 1 ) : dp [ ][ i ] = values [ ] for i in range ( 1 , n ) : for j in range ( k + 1 ) : if weights [ i ] > j : dp [ i ][ j ] = dp [ i - 1 ][ j ] else : dp [ i ][ j ] = max ( v alues [ i ] + dp [ i - 1 ][ j - weights [ i ]], dp [ i - 1 ][ j ]) return dp [ n - 1 ][ k ]

132. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range ( weights [ ], k + 1 ) : dp [ ][ i ] = values [ ] for i in range ( 1 , n ) : for j in range ( k + 1 ) : if weights [ i ] > j : dp [ i ][ j ] = dp [ i - 1 ][ j ] else : dp [ i ][ j ] = max ( v alues [ i ] + dp [ i - 1 ][ j - weights [ i ]], dp [ i - 1 ][ j ]) return dp [ n - 1 ][ k ]              

133. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) dp = [[ ] * ( k + 1 ) for i in range ( n )] for i in range ( weights [ ], k + 1 ) : dp [ ][ i ] = values [ ] for i in range ( 1 , n ) : for j in range ( k + 1 ) : if weights [ i ] > j : dp [ i ][ j ] = dp [ i - 1 ][ j ] else : dp [ i ][ j ] = max ( v alues [ i ] + dp [ i - 1 ][ j - weights [ i ]], dp [ i - 1 ][ j ]) return dp [ n - 1 ][ k ]    

134. def knapsack ( values , weights , k ) : if k == : return elif k >= sum ( weights ) : return sum ( values ) n = len ( values ) prev_dp = [ ] * ( k + 1 ) dp = [ ] * ( k + 1 ) for i in range ( weights [ ], k + 1 ) : prev_dp [ i ] = values [ ] for i in range ( 1 , n ) : for j in range ( k + 1 ) : if weights [ i ] > j : dp [ j ] = prev_dp [ j ] else : dp [ j ] = max ( values [ i ] + prev_dp [ j - weights [ i ]], prev_dp [ j ]) prev_dp = dp dp = [ ] * ( k + 1 ) return prev_dp [ k ]      

135. 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 30 30 50 50 20 20 20 20 20 20 20 35 35 35 35 35 35 50 50 20 20 20 20 25 25 25 35 35 35 45 45 45 50 50 10 10 10 20 20 20 30 30 30 30 35 35 35 45 45 45 55 55 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 k ( 17 , 5 ) k ( 14 , 5 ) k ( 11 , 5 ) k ( 10 , 5 ) k ( 7 , 5 ) k ( 4 , 5 ) k ( 3 , 5 ) k ( 1 , 5 ) k ( , 5 ) k ( 20 , 5 ) k ( 20 , 2 ) k ( 20 , 3 ) k ( 7 , 2 ) k ( 1 , 2 ) k ( 14 , 2 ) k ( 7 , 3 ) k ( 1 , 3 ) k ( 14 , 3 ) k ( 20 , 1 ) k ( 14 , 1 ) k ( 20 , ) k ( 20 , 4 ) k ( 7 , 4 ) k ( 1 , 4 ) k ( 14 , 4 ) k ( 13 , 3 ) k ( , 3 ) k ( 10 , 4 ) k ( 4 , 4 ) k ( 3 , 4 ) k ( , 4 ) k ( 13 , 4 ) k ( 13 , 3 ) input: values = [ 20 , 30 , 15 , 25 , 10 ] weights = [ 6 , 13 , 7 , 10 , 3 ] k = 20

136. 0-1 knapsack