how can i solve this problem

Правка en7, от mustafaeren, 2024-03-29 16:35:26

There are N items with weights $$$w_i$$$ and values Ei. We need to choose some items such that sum of their values(ei) is X and sum of their weights(wi) is minimum. The values of items are given as exponent of 2.

The first line contains 2 integers:\ 2≤N≤10^7(number of items)\ 1≤X<2^1000(target sum of values)\

The next N lines contain 2 integers:
0≤ei≤999(Exponent of the value of the item)
1≤wi≤10^9(Weight of the item)

example :

input:
5 34
0 1
0 2
0 3
1 25
5 12

output: 15

Теги dynamic programming, bit, knapsack

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский mustafaeren 2024-03-29 16:39:46 35 (published)
en10 Английский mustafaeren 2024-03-29 16:38:09 6
en9 Английский mustafaeren 2024-03-29 16:37:30 55
en8 Английский mustafaeren 2024-03-29 16:35:51 8 Tiny change: 'integers:\\\n2≤N≤10^7' -> 'integers:\newline\n2≤N≤10^7'
en7 Английский mustafaeren 2024-03-29 16:35:26 41
en6 Английский mustafaeren 2024-03-29 16:33:29 50
en5 Английский mustafaeren 2024-03-29 16:27:25 30
en4 Английский mustafaeren 2024-03-29 16:25:19 2 Tiny change: '<br>\n2≤N≤10^7(number of' -> '<br>\n2≤N≤$10^7$(number of'
en3 Английский mustafaeren 2024-03-29 16:22:09 4 Tiny change: '\n\ninput:\n5 34<br>' -> '\n\ninput:<b\n5 34<br>'
en2 Английский mustafaeren 2024-03-29 16:21:46 44
en1 Английский mustafaeren 2024-03-29 16:13:33 524 Initial revision (saved to drafts)