fork download
copy 
  1. def greedy_knab(weight, profit, size, capacity, used=None):
  2.     if used is None:
  3.         used = []
  4.  
  5.     if capacity <= 0:
  6.         global path1   
  7.         path1=used
  8.         return 0
  9.  
  10.     max = profit[0]
  11.     chosen_one = -1
  12.     for i in range(size):
  13.         if i not in used and weight[i] <= capacity:
  14.             if profit[i] >= max:
  15.                 max = profit[i]
  16.                 chosen_one = i
  17.     if chosen_one == -1:
  18.         path1=used
  19.         return 0
  20.     used.append(chosen_one)
  21.     return profit[chosen_one] + greedy_knab(weight, profit, size, capacity - weight[chosen_one],used)
  22.  
  23. def dp_knapsack(dp, weight, profit, size, capacity, cur_capacity=0, i=0, sum=0, pick=[]):
  24.     global ans, picked
  25.     if i >= size:
  26.         if i == size and ans < sum:
  27.             ans = sum
  28.             picked = copy.deepcopy(pick)
  29.         return
  30.     if dp[i][cur_capacity] != -1 and dp[i][cur_capacity] >= sum:
  31.         return
  32.     dp[i][cur_capacity] = sum
  33.     # leave
  34.     dp_knapsack(dp, weight, profit, size, capacity, cur_capacity, i+1, sum, pick)
  35.  
  36.     # pick
  37.     if cur_capacity + weight[i] <= capacity:
  38.         pick.append(i)
  39.         dp_knapsack(dp, weight, profit, size, capacity, cur_capacity + weight[i], i + 1, sum + profit[i], pick)
  40.         pick.pop()
  41.  
  42. def recurse_knapsack(weight, profit, size, capacity, cur_capacity=0, i=0, sum=0, pick=[]):
  43.     global ans, picked
  44.     if i >= size:
  45.         if i == size and ans < sum:
  46.             ans = sum
  47.             picked = copy.deepcopy(pick)
  48.         return
  49.  
  50.     # pick
  51.     if cur_capacity + weight[i] <= capacity:
  52.         pick.append(i)  # do
  53.         recurse_knapsack(weight, profit, size, capacity, cur_capacity + weight[i], i + 1, sum + profit[i], pick) # recruse
  54.         pick.pop() # undo
  55.  
  56.     # leave
  57.     recurse_knapsack(weight, profit, size, capacity, cur_capacity, i + 1, sum, pick)
  58.  
  59. def table_knapsack(weight, profit, size, capacity):
  60.     dp = [[0] * (capacity + 1) for _ in range(size + 1)]
  61.     for i in range(1, size + 1):
  62.         for w in range(1, capacity + 1):
  63.             if w >= weight[i - 1]:
  64.                 dp[i][w] = max(profit[i - 1] + dp[i - 1][w - weight[i - 1]], dp[i - 1][w])
  65.             else:
  66.                 dp[i][w] = dp[i - 1][w]
  67.     return dp
  68.  
  69. def get_selected_indices(dp):
  70.     picked = []
  71.     wt = len(dp[0]) - 1
  72.     i = len(dp) - 1
  73.     while wt > 0 and i > 0:
  74.         if dp[i][wt] != dp[i - 1][wt]:
  75.             picked.append(i - 1)
  76.             wt -= weight[i - 1]
  77.         i -= 1
  78.     return picked
  79.  
Success #stdin #stdout 0.02s 7092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E86EM9
language:
Python (cpython 2.7.16)
created:
4 days 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!