How can i solve this problem ? (knapsack with exponents of 2)

Правка en11, от mustafaeren, 2024-03-29 16:39:46

There are N items with weights $$$w_i$$$ and values $$$e_i$$$. We need to choose some items such that sum of their values($$$e_i$$$) is equal to X and sum of their weights($$$w_i$$$) is minimum. The values of items are given as exponents 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≤e_i≤999$$$(Exponent of the value of the item)
$$$1≤w_i≤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)