Guest User

Untitled

a guest
Sep 4th, 2020
54
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def solve(i,budget,n,h,p,dp):
  2.     if(budget==0 or i==-1):
  3.         return 0
  4.     if(dp[i][budget]!=-1):
  5.         return dp[i][budget]
  6.     x,y=0,0
  7.     if(budget-h[i]>=0):
  8.         x=p[i]+solve(i-1,budget-h[i],n,h,p,dp)
  9.     y=solve(i-1,budget,n,h,p,dp)
  10.     dp[i][budget]=max(x,y)
  11.     return dp[i][budget]
  12.  
  13.  
  14. n,x=map(int,input().split())
  15. h=list(map(int,input().split()))
  16. p=list(map(int,input().split()))
  17. dp=[[-1 for i in range(x+1)]for j in range(n+1)]
  18. print(solve(n-1,x,n,h,p,dp))
  19.  
RAW Paste Data