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
"Powers of 2 are always in the form 00001, 00010, 00100, and so on. Therefore, check first if all the 'on' bits in the target sum are available with you. Let's assume that for the 'i-th' bit, I have two available items. Then, just choose the minimum weight of them."
İnstead of using one from the i-th bit we can use 2 from i-1 -th bit or 4 from i-2 th bit or combinations of them.
Knapsack each bit first. Is taking 2 i-1 cheaper than 1 i.
i-1 is not the only case you can take 2 from i-1 or 4 from i-2 and so on.. so it's more complicated
If 4 i-2 is better than 2 i-1, why you didn't set i-1 to 2 i-2 on previous step then?
what happens if we have 10 for the 5th bit 3, 4, 50 for the 4 th bit and the target has ones on both 5th and 4th bits ?
can you write the transition of the dp ?
yes you are correct I didn't think about that
anyone ?
I solved it by first converting string $$$X$$$ to it's binary representation which is stored in target. Then I go through every bit from most significant to least. I take all of the amount of values i can from that bit and i pass the leftovers to the next bit by multiplying the leftover by 2. I believe it works in $$$O(10^{10})$$$ which is not enough.
Here is my code:
We can iterate from least significant bit to most significant bit in $$$X$$$. Suppose we're at the $$$i$$$th bit, and our choices for weights in sorted order are $$$w_1, w_2, ..., w_m$$$ (I know that bits at positions $$$< i$$$ can contribute, but read on). The number of bits that we'll pick is odd iff the $$$i$$$th bit is on in $$$X$$$. If so, add $$$w_1$$$ to the answer and then get rid of it. Then, consider $$$w_1 + w_2, w_3 + w_4, w_5 + w_6, ...$$$ and add those as options for the $$$i + 1$$$th bit. The complexity is $$$O(n \log n)$$$ and you can use pqs to store the weights — there are $$$O(n)$$$ weights inserted in total because:
Let every item added to some pq be a vertex in a graph. From every item that came from the sum of $$$2$$$ other items, draw an edge from that item to the $$$2$$$ other guys. We have a forest of binary trees. Since there are $$$n$$$ leaves, the forest must have at most $$$2n - 1$$$ vertices.