daily pastebin goal
59%
SHARE
TWEET

Untitled

Bad_Programist Feb 20th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. N, M = list(map(int, input().split()))
  2. W = list(map(int, input().split()))
  3. P = list(map(int, input().split()))
  4. A = [[0] * (M + 1) for i in range(N + 1)]
  5. for i in range(1, N + 1):
  6.     for j in range(1, M + 1):
  7.         if W[i - 1] > j:
  8.             A[i][j] = A[i - 1][j]
  9.         else:
  10.             A[i][j] = max(A[i - 1][j], P[i - 1] + A[i - 1][j - W[i - 1]])
  11. i = N
  12. j = M
  13. R = []
  14. while i != 0:
  15.     while A[i][j] == A[i][j - 1]:
  16.         j -= 1
  17.     if A[i][j] > A[i - 1][j]:
  18.         R.append(i)
  19.     i -= 1
  20. for i in sorted(R):
  21.     print(i)
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