jlcastrillon's blog

How to solve it??
By jlcastrillon, 12 years ago, In English

This problem looks like knapsack with repetition but limits are huge and I can't find a solution using DP, Could anyone tell me how to solve it, here is the link. http://poj.org/problem?id=3900

I have seen this kind of problems several times but I have never been able to solve them. Thanks in advance....

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

»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

N is not too big, so you can test all subsets of a given set. For each subset you can calculate its weight and cost in linear time. It's a O(N·2N) per test solution, and it seems to be OK.

UPD: that's not a solution, I didn't get the problem corerctly.

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

    Inside the box with number k there are k very big diamonds, each of weight Wk and cost Ck.

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

But how if each element can be taken several times...

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

    Sorry, I misread the statement and was wrong. So, in the correct problem N is less or equal then 120.

    I don't think that there exists a polynomial solution. Maybe meet in the middle or something, but I can't see get it right now. Anyway, maybe bactracking with good pruning and greedy optimisations, simulated annealing or other heuristics like these can get AC (but not solve the problem).

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

      120? Correct problem? Please explain this moment, i don't get it.
      Meet-in-the-middle is simple, but too slow. we can divide diamonds into two groups 1..10 and 11..15, for each of the groups brute-force answers, then sort two arrays of pairs (weight, cost). now we can find in linear time (using two's pointers method) two elements with total weight less than or equal to M and with maximal cost.

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

        I meen there are 120 possible diamonds. (1 from first box, 2 from second etc). I know. That's why I didn't find a solution yet :) How do you want to brute-force answers for each group? They are large enough, too. Or you mean backtracking with heuristics?

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

          there is only 11! answers for first group and 12 * 13 * 14 * 15 * 16 for second.

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

            You're right again! I have an exam tomorrow, and my head is going to blow up. I can't see obvious things. I'd better postpone thinking about problems until tomorrow evening.

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

        Excuse me, I tried to write solution using your idea, but this code gets ML and I cannot figure out why!
        Can anyone explain my trouble?
        Maximum size of vector must be about 10!  ≈  3·106.
        Sorry for my poor english...

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

          Because it's wrong solution. As i said it is too slow (and uses too many memory). Memory limit is 65536K one of yours vectors uses 12 * 3 * 10^6 bytes (in the ideal test case, vector can use twice more memory than it have to use, because of it's implementation) you can try to reserve memory a[0].reserve(10!). But it will be TL.

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

            Oh...I forgot that we have 16! answers (not 15!) and maximum size is 4586400 = 3·5·7·13·14·15·16.
            I should read comments carefully...
            Anyway, thanks for your advice!

            → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I don't know for sure, and i can't prove this, but it seems to be true: we must to find solution for the case when we steal something that can be divided as we want (for example different types of the sand) solve problem for this case (it's easy, we must to take the most expensive sand as many as we can). Now solutions for this problem differs only by +/-1 for each type. Let we have solution S for "sand problem". S[i] means how many sand of type I must be taken. We want to know real solution R, i think R[i] is equal to Floor(S[i]) or Ceil(S[i]). Floor(X) is the nearest integer less than or equal to X, Ceil(X) is the nearest integer greater than or equal to X.

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

    I must be wrong, it' seems like there must be O(2^n*poly) or O(3^n)
    In the opposite case N can be bigger. Also, there will be only one element of S with realy REAL value.

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

    And what about this solution? We look through subsets. If current box is in the subset, then R[i] = floor(S[i]), otherwise R[i] = ceil(S[i]). This is correct if your suggestion about +/-1 is correct.

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

      Oh, I didn't see your previous post. Only one of S[i] is real, so probably it's not correct. Keep thinking.

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

      I thought about that, when think about this solution, but then I have realized that there is only one real REAL value :)

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

      So, maybe we have to look through all subsets, Let's keep thinking in this direction... Maybe there is another S, which have this property?

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

This problem seems hard,but actually just simply search with some insightful pruning ( and reorder the items by some greedy idea) can succeed.

→ Reply