daily pastebin goal
26%
SHARE
TWEET

Untitled

a guest Jan 14th, 2018 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. MAX_N = 100
  2. MAX_W = 10000
  3.  
  4. knap = [
  5.     {'weight':2, 'value':3},
  6.     {'weight':1, 'value':2},
  7.     {'weight':3, 'value':4},
  8.     {'weight':2, 'value':2}
  9.     ]
  10.  
  11. def main():
  12.     W, N = 5, 4
  13.     dp = [[0 for _ in range(MAX_W)] for _ in range(MAX_N)]
  14.  
  15.     for i in range(N):
  16.         for j in range(W+1):
  17.             if j < knap[i]['weight']:
  18.                 dp[i+1][j] = dp[i][j]
  19.             else:
  20.                 dp[i+1][j] = max(dp[i][j], dp[i][j-knap[i]['weight']]+knap[i]['value'])
  21.     print dp[N][W]
  22.  
  23. if __name__ == '__main__':
  24.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top