mustafaeren's blog

How can i solve this problem ? (knapsack with exponents of 2)
By mustafaeren, history, 4 weeks ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

"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."

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    İ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.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Knapsack each bit first. Is taking 2 i-1 cheaper than 1 i.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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?

          → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you write the transition of the dp ?

        → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes you are correct I didn't think about that

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone ?

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

Spoiler
→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply