fork download
copy 
  1. import sys
  2.  
  3. def main():
  4.     input_data = sys.stdin.read().splitlines()
  5.     lines = [line.strip() for line in input_data if line.strip()]
  6.  
  7.     if not lines:
  8.         return
  9.  
  10.     W = int(lines[0])
  11.     weights = list(map(int, lines[1].split()))
  12.     values = list(map(int, lines[2].split()))
  13.     n = len(weights)
  14.  
  15.     dp = [[0] * (W + 1) for _ in range(n + 1)]
  16.  
  17.     for i in range(1, n + 1):
  18.         w = weights[i-1]
  19.         v = values[i-1]
  20.         for j in range(W + 1):
  21.             if j < w:
  22.                 dp[i][j] = dp[i-1][j]
  23.             else:
  24.                 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
  25.  
  26.     i = n
  27.     j = W
  28.     selected_items = []
  29.  
  30.     while i > 0 and j > 0:
  31.         w = weights[i-1]
  32.         v = values[i-1]
  33.  
  34.         if j < w or dp[i-1][j] >= v + dp[i-1][j - w]:
  35.             i -= 1
  36.         else:
  37.             selected_items.append(i)
  38.             j -= w
  39.             i -= 1
  40.  
  41.     selected_items.sort()
  42.     print(*selected_items)
  43.  
  44. if __name__ == '__main__':
  45.     main()
Success #stdin #stdout 0.11s 14024KB
comments (?)
stdin
copy 
10
1 4 7 3 4 9
4 3 9 1 7 5
stdout
copy 
1 2 5
https://ideone.com/tzwngk
language:
Python 3 (python  3.12)
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!