how can i solve this problem

Revision en2, by mustafaeren, 2024-03-29 16:21:46

There are N items with weights Wi 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

Tags dynamic programming, bit, knapsack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English mustafaeren 2024-03-29 16:39:46 35 (published)
en10 English mustafaeren 2024-03-29 16:38:09 6
en9 English mustafaeren 2024-03-29 16:37:30 55
en8 English mustafaeren 2024-03-29 16:35:51 8 Tiny change: 'integers:\\\n2≤N≤10^7' -> 'integers:\newline\n2≤N≤10^7'
en7 English mustafaeren 2024-03-29 16:35:26 41
en6 English mustafaeren 2024-03-29 16:33:29 50
en5 English mustafaeren 2024-03-29 16:27:25 30
en4 English 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 English mustafaeren 2024-03-29 16:22:09 4 Tiny change: '\n\ninput:\n5 34<br>' -> '\n\ninput:<b\n5 34<br>'
en2 English mustafaeren 2024-03-29 16:21:46 44
en1 English mustafaeren 2024-03-29 16:13:33 524 Initial revision (saved to drafts)