vlyubin's blog

Online knapsack
By vlyubin, 10 years ago, In English

Can someone help me with solving a problem of online knapsack with small constraints. Formally: you have a knapsack that can fit items of weight at most W. You are given N queries, where each query is one of:

  • Add a new item of weight w and cost s to a set of possible objects.

  • Remove the oldest item from the set of possible objects (the one which was added to the set before others)

  • Solve knapsack — print the largest cost you can achieve by choosing some objects from your current set so that their combined weight is at most W.

Constraints:

  • W <= 2000 (fixed and is given to you)

  • N <= 10000

  • Cost <= 1000000

  • There can be at most L = 2000 items in your set of objects at any time.

  • TL: 5 seconds

Example (W = 100):

  • Add (w=20,c=30)

  • Add (w=20,c=35)

  • Query: C=65

  • Remove

  • Query: C=35

There are a LOT of articles about online knapsack problem out there, but most of them try to approximate the result. In this case, we have a pretty small constraint on W, but I cannot take advantage of this. The naive approach (do a DP each time a knapsack query comes along) gets a TL.

Source: https://www.hackerrank.com/contests/cs-quora/challenges/quora-feed-optimizer

Thanks!

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

Comments Comments (12)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

"TL: 5 seconds" Don't you mean 0.5s or the real TL is 5s? Okay... I think your dp uses a state f[i][j] which is the maximum cost if we use the first i knapsacks and the weight is j. You don't really need to compute all the values when you have to solve the knapsack. Let cnt be the number of objects in the set and let us assume that we have computed f[i][j] for i<=cnt.

If you have to remove an object just decrease cnt by 1;

If you have to add an object increase cnt by 1 and compute each state from f[cnt][0] to f[cnt][W];

If you have to compute the knapsack just find the maximum value from the set{f[cnt][0], f[cnt][1] ,..., f[cnt][W]};

Time complexity: O(W*N)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    as I understand , You solved the problem if the remove operation is to remove the newest item , but he's asking about removing the oldest

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes, you are right! :( I'll think again.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Instead let dp[i][j] (i:1..N, j:0..W) be the best profit if items from 1 to i with j weight.

        Use a monotone queue to maintain the maximal element in the range.

        Insert: Update dp[(current last item][0..W]. Push all element updated to the queue with pair {dp[(current last item][0..W], [number of current last item]}. Update best answer as the head of the queue.

        Delete: Remove all the outdated data (i.e. the current earliest item exceeds the second id of the queue), Update best answer.

        Query: Output.

        Complexity: O(NW)

        UPD: If you know nothing about monotone queue, check google.

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

          Could you explain the procedures in a bit more detail? I'm having trouble figuring out how the algorithm works.

          → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It can be done with complexity.

One can handle erase operations with decomposition.

Hint: try to use few insert instead of a erase.

PS: Im not sure about it will pass or not but i would implement it since time limit is 5 secs. If it is too slow, think about divide and conquer approach.

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

This problem can be solved in O(NW).

For erase only problem (You get the full list in advance, and erase from the head), you only need build a table backwardly (use the method P_Nyagolov mentioned, in a reversed way). O(W) time for each element.

For insert only problem, you can build a table forwardly. O(W) time for each element.

What you need is just combine this two tasks. So you have two tables, a forward one for insert, and a backward one for erase. So when query, you need to combine this two tables, with O(W) time for each query.

The only problem left is what to do when you erased all elements from the backward table. I would say, just rebuild a new backward table for all elements you currently have. For U lefted elements, it takes O(UW) time. Since every element can only be used once here, the total time used is O(NW).

Since we have restriction on L, so the space usage would be O(LW).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you explain how do you combine the two tables?

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

      So you don't need really combine the entire tables, what you need is to answer the query.

      When you have two tables, one for A elements, and the other one for rest B elements. You just need to enumerate how much capacity of the backpack you would like to give for the first table. Let's say C, so the rest capacity W-C you will give to the B elements. The answer would be max(table1[A][C]+table2[B][W-C], C=0..W).

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

    This sounds great! How do you combine two tables in O(W) though?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it +10 Vote: I do not like it

      See my reply to kingofnumbers.

      Let's say a simpler problem for better understanding. We have 3 operations: insert, erase, and ask for sum of all elements.

      We maintain two stacks, A and B, and two sum arrays stores the sum of elements from i to the bottom of the stack. sumA[i] = sum(A[i..1]) sumB[i] = sum(B[i..1])

      The algorithm would be:

      insert x:
  B.push(x);
  sumB[topB] = sumB[topB-1] + x

erase: 
  if not A.hasElements():
    A = reverse B; construct sumA;
    B.clear();
  A.pop();

query:
  return sumA[topA]+sumB[topB];
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, your idea is clear now, I've met a multiple-choice question that says: how many stacks do you need to make a queue? I thought the answer is "impossible" but now you showed that we can make a queue using 2 stacks :)

        → Reply