WALL-E__'s blog

KNAPSACK PROBLEM-DP
By WALL-E__, history, 6 years ago, In English

i am having problem in solving this problem using 0/1 knapsack problem. http://codeforces.com/contest/19/problem/B

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

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You need to keep two states:

I: Current item.

R: Number of items remaining.

The transition is, take the item I paying ci and go to the item I + 1 with R - 1 - ti remaining items, or dont take the item I and go to the item I + 1 with R remaining items.

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

There's a simple solution that runs in O(2N). Just try all combinations and keep the best.

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

    But 1 ≤ N ≤ 2000, do you have some super computer ?

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

      Well, not me, but the studios where I usually work make 3D movies too, so they have a farm of around 45 powerful computers running at the same time.

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

        Wow, in how many seconds them run 22000 operations ?, can you give me one powerful computer ?

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

          Well, you can do the math. One powerful computer can do 1000 million operations per second, which is around 230, so it can do 60 * 230 in a minute. That's around 236 in a minute and 242 in one hour, so it would take something like 21958 hours to run the solution. One year has 213 hours approximately, so it will take 21945 years. Is it good enough?

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

            Complexity if exponential, but you can get it to run under 1000ms (in java) using the sleep.thread() trick. This should be common knowlegde.

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

              Indeed, or you can use #pragma lightspeed in C++55, which will be released in 37 years. But since it uses black hole quantum physics to compile and run, it doesn't matter, you can use it today by calling that pragma.

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

                So it turns out C++ really is better at everything. I think using a bitset will reach O(1/n) (watch out for n = 0) complexity, but seems that its too difficult for a simple problem as this

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

                  well they didn't make minecraft in c++ did they

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

    Maybe with more pruning than luck code. I use a branch and bounds algorithm with the upper bound $$$U_2$$$.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Another way is [itemupto][time] with observation time > 2000 dont matter. do we store dp[item][time] = minimum cost.

Note that for each item we can "add" 1 second to it because it takes care of itself.

And we us the dp table to solve problem.

EDIT: Wow it seems I've greatly infected the integrity of CF by giving out correct solutions! The horror!

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

    Seems people doubt the accuracy of my previous comment. Well, my method works and it's implementation is short:

    http://codeforces.com/contest/19/submission/44525896

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

    Cool man doesn't look at the explosion.

    Cool codeforces-er doesn't edit comment after being downvoted (I think).

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

      yeah if you look back at the explosion you gonna get hit by shrapnel, thats how movies work

      but yeah dont subject me to your personal definition of "cool"

      → Reply