Jan 092009
 

ZJU 3077 – Move to Baggage Office

There are N item to be moved and you have initial strength S. Each item has three properties, vi – the value of this item, ai – the strength cost to move this item, bi – the strength you will regain after moving this item. Your strength should be at least ai to move the ith item.

You maybe unable to move all items, so you want to find the maximum value that you can gain.


This problem can be solved by dp-knapsack with the items are first sorted in decreasing order of bi. Remember that dp-knapsack will work only when the item ordering is not important (so we don’t need to “look back” after processing each item), thus we need the preprocessing step.

Let’s observe the ordering of two items: item1 (a1, b1) and item2 (a2, b2). The after-strength if we take both items will always the same in spite of the ordering, but the total strength needed will be different depends on which bi is larger. If item1 is taken before item2, then the needed strength will be (a1 – b1 + a2). But if item2 is taken first, then the it will be (a2 – b2 + a1). It’s obvious that one with larger bi will yield the lowest needed strength.

  3 Responses to “ZJU 3077 – Move to Baggage Office”

  1. Waw.., sepertinya lagi berlatih soal2 DP terus nih?
    hehehe… πŸ˜€ Nice Analysis..

  2. hmm… itu dp karena kebetulan aja solusinya bisa begitu, bukan karena sengaja nyari soal dp.

    gw cuma iseng nyari soal-soal yg keliatannya “menarik” (pas dibaca gak langsung keliatan solusinya), jadi kudu mikir dulu. kan gak seru kalau sebelum mulai udah tau harus pake apa (spoiler) πŸ™‚

  3. Iya juga sih…, lebih seru ya kalo harus mikir dulu..
    Lebih ada tantangannya gitu.. πŸ˜€

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)