荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: 背包问题
发信站: 荔园晨风BBS站 (Fri Sep  3 10:17:10 2004), 站内信件

                          Knapsack Problems


Prerequisite modules

    * Greedy
    * Dynamic Programming
    * Recursive Descent

Sample Problem: Tape Recording

Farmer John's favorite hobby is creating a tape containing some of Bess
ie's favorite music to listen to while she's being milked. The amount of
 milk that Bessie produces is dependent on the songs that Bessie listens
 to while being milked.

Given a collection of songs, each represented by a pair of integers, th
e length of the song (in seconds), the amount of milk Bessie produces wh
ile she's listening to that song, and the total amount of time that it t
akes to milk Bessie, find the set of songs such that their total length
is no more than the time it takes to milk Bessie and they maximize Bessi
e's milk production.
The Abstraction

Given, A collection of objects, each which a size, a value (i.e., weigh
t), and the total `space' available, find the set of objects which maxim
izes the sum of the value of the set, but whose sum of size is constrain
ed by some limit. The total number/size of any particular item used in t
he set cannot exceed its availability.
Problem Viewpoint

The general way to view a knapsack problem is that of a bag of limited
capacity, which is to be filled while maximizing the value of the object
s in it.

For the problem above, the tape which Bessie will listen to while being
 milked is the ``knapsack,'' while the songs are the ``objects to be pla
ced within the knapsack.''
Three Knapsack Problems

The knapsack problem style has three forms:

    * Fractional knapsack problem
      A fractional knapsack problem is one in which you are allowed to
place fractional objects in the knapsack. For example, if the objects we
re crude oil, airplane fuel, and kerosene and your knapsack a bucket, it
 might make sense to take 0.473 liter of the crude oil, 0.263 liter of t
he airplane fuel, and 0.264 liter of the kerosene. This is the easiest f
orm of the knapsack problem to solve.
    * Integer Knapsack problem
      In integer knapsack problems, only complete objects can be insert
ed into the knapsack. The example problem is of this form: partial songs
 aren't allowed.
    * Multiple knapsack problem
      In the multiple knapsack problem, more than one knapsack is to be
 filled. If fractional objects are allowed, this is the same as having o
ne large knapsack with capacity equal to the sum of all the available kn
apsacks, so this term will only be used to refer to the case of multiple
 integer knapsacks.

Fractional knapsack problem

The fractional knapsack problem is the easiest of the three to solve, a
s the greedy solution works:

    * Find the object which has the highest ``value density'' (value of
 object / size).
    * If the total amount of capacity remaining exceeds the availabilit
y of that object, put all of it in the knapsack and iterate.
    * If the amount of capacity is less than the availability of the ob
ject, use as much as possible and terminate.
    * This algorithm runs in N log N since it must sort the objects fir
st based on value density and then put them into the knapsack in decreas
ing order until the capacity is used. It's normally easier to not sort t
hem but rather just keep finding the highest value density not used each
 time, which gives a O(N 2) algorithm.

Side note: For problems of this class, it's rare to have both size and
availability, as you can do a trivial transformation to have all the obj
ects of size 1, and the availability be the product of the original size
 and availability (dividing the value by the original size, of course).

Extensions: The value and availability of the objects can be real numbe
rs without a problem in this case. The fractional size issue is also tri
vial to handle by this algorithm.
Integer knapsack problem

This is slightly more difficult, but is solvable using dynamic programm
ing if the knapsack is small enough.

    * Do dynamic programming on the maximum value that a knapsack of ea
ch size can have in it.
    * Update this array for an object of size S by traversing the array
 in reverse order (of capacity), and seeing if placing the current objec
t into the knapsack of size K yields a better set than the current best
knapsack of size K+S.
    * This algorithm runs in K x N time, where K is the size of the kna
psack, and N is the sum of availability of objects.
    * If the knapsack is too large to allocate this array, recursive de
scent is the method of choice, as this problem is NP-complete. Of course
, recursive descent can run for a very long time in a large knapsack bei
ng filled with small objects.

Extensions:

    * Fractional values are not a problem; the array just becomes an ar
ray of real numbers instead of integers. Fractional availability doesn't
 affect things, as you can, without loss of generality, truncate the num
ber (if you have 3.5 objects, you can only use 3).
    * Fractional size is a pain, as it makes the problem recursive desc
ent.
    * If the sizes are all the same, the problem can be solved greedily
, picking the objects in decreasing value order until the knapsack is fu
ll.
    * If the values are all 1.0, then again greedy works, selecting the
 objects in increasing size order until the knapsack is full.

Multiple knapsack problem

With multiple knapsacks of any size, the state space is too large to us
e the DP solution from the integer knapsack algorithm. Thus, recursive d
escent is the method to solve this problem. Extensions:

    * With recursive descent, extensions are generally easy. Fractional
 sizes and values are no problem, nor is another evaluation function.
    * If the values are all one, then if the maximum number of objects
that can be placed in all the knapsacks is n, then there is such a solut
ion which uses the n smallest objects. This can greatly reduce the searc
h time.

Sample Problems
Score Inflation [1998 USACO National Championship]

You are trying to design a contest which has the maximum number of poin
ts (<10,000). Given the length of the contest, a group of problems, the
problem lengths, and the point value of each problem, find the contest w
hich has the maximum number of points (which satisfies the length constr
aint).

Analysis: This is an integer knapsack problem, where the knapsack is th
e contest, the sizes are the length of problems, and the values are the
point values. The limit on knapsack (contest) size is small enough that
the DP solution will work in memory.
Fence Rails [1999 USACO Spring Open]

Farmer John is trying to construct a fence around his field. He has ins
talled the posts already, so he knows the length requirement of the rail
s. The local lumber store has dropped off some boards (up to 50) of vary
ing length. Given the length of the boards from the lumber store, and th
e lengths of rails that Farmer John needs, calculate the maximum numbers
 of rails that Farmer John can create.

Analysis: This is a multiple knapsack problem, where the knapsacks are
the boards from the store, and the objects are the rails that Farmer Joh
n needs. The size of the objects are just the length, and the value is j
ust one.

Since the values are all one, you know that if there is a solution usin
g any K rails, there is a solution using the K smallest rails, which hel
ps the recursive descent solver quite a bit.
Filling your Tank

You're in the middle of Beaver County, at the only city within 100 mile
s with a gas station, trying to fill up your tank so you can get to Rita
 Blanca. Fortunately, this town has a couple of gas stations, but they a
ll seem to be almost out of gas. Given the price of gasoline at each sta
tion, and the amount of gas each one has, calculate how much gasoline to
 buy from each station in order to minimize the total cost.

Analysis: This is an fractional knapsack problem, where your knapsack i
s your gas tank, and the objects are gasoline.

--
       灬 灬 灬灬 灬灬  灬 灬 ════════════════════╗╮
   ╭╯  灬 灬▂╱   _灬灬ジ  ヾ                                   灬╰╗
   ║ 灬◢◢ "▔ 灬╱          灵台无计逃神矢  风雨如磐暗故园  ▁  灬|"|║
   ║     ◤,  |,╱_ ◣◣      寄意寒星荃不察  我以我血荐轩辕▕心▏  ◣|║
   ║     _,|\▄/ \▌◥                                        ▔ヾ◥◥|║
   ╚═ "\▌| ▔ | | /" ════════════════════════╯

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店