Advertisement
Bad_Programist

Untitled

Feb 20th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.51 KB | None | 0 0
  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.     if A[i][j] > A[i - 1][j]:
  16.         R.append(i)
  17.         j -= W[i - 1]
  18.     i -= 1
  19. for i in sorted(R):
  20.     print(i)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement