The knapsack model classically deals with the situation in which a soldier (or a hiker) must decide on the most valuable items to carry in a backpack. The problem paraphrases a general resource allocation model in which a single limited resource is assigned to a number of alternatives (e.g., limited funds assigned to projects) with the objective of maximizing the total return.
Before presenting the DP model, we remark that the knapsack problem is also known in the literature as the fly-away kit problem, in which a jet pilot must determine the most valuable (emergency) items to take aboard a jet; and the cargo-loading prob-lem, in which a vessel with limited volume or weight capacity is loaded with the most valuable cargo items. It appears that the three names were coined to ensure equal rep-resentation of three branches of the armed forces: Air Force, Army, and Navy!
The (backward) recursive equation is developed for the general problem of an n-item W-Ib knapsack. Let mi be the number of units of item i in the knapsack and define ri and wi as the revenue and weight per unit of item i. The general problem is represented by the following ILP:
Step 2. Express xi+1 as a function of xi to ensure that the left-hand side, fi(xi), is a function of xi only. By definition, xi - xi+1 = wimi represents the weight used at stage i. Thus, xi+1 = xi - wimj, and the proper recursive equation is given as
A 4-ton vessel can be loaded with one or more of three items. The following table gives the unit weight, wi, in tons and the unit revenue in thousands of dollars, ri, for item i. How should the vessel be loaded to maximize the total return?
Because the unit weights wi and the maximum weight W are integer, the state xi assumes integer values only.
Stage 3. The exact weight to be allocated to stage 3 (item 3) is not known in advance, but can assume one of the values 0,1, ... , and 4 (because W = 4 tons). The states x3 = and x3 = 4, respectively, represent the extreme cases of not shipping item 3 at all and of allocating the entire vessel to it. The remaining values of x3 (= 1,2, and 3) imply a partial allocation of the vessel capacity to item 3. In effect, the given range of values for x3 covers all possible allocations of the vessel capacity to item 3.
Given w3 = 1 ton per unit, the maximum number of units of item 3 that can be loaded is
4/l = 4, which means that the possible values of m3 are 0, 1,2,3, and 4. An alternative m3 is feasible only if w3m3 ≤ x3. Thus, all the infeasible alternatives (those for which w3m3 > x3 ) are excluded. The following equation is the basis for comparing the alternatives of stage 3.
The optimum solution is determined in the following manner: Given W = 4 tons, from stage 1, x1 = 4 gives the optimum alternative mi* = 2, which means that 2 units of item 1 will be loaded on the vessel. This allocation leaves x2 = x1 - 2m2* = 4 - 2 X 2 = 0. From stage 2, x2 = 0 yields m2* = 0, which, in turn, gives x3 = x2 - 3m2 = 0 - 3 X 0 = 0. Next, from stage 3, x3 = 0 gives m3* = 0. Thus, the complete optimal solution is mi* = 2, m2* = 0, and m3* = 0. The associated return is f1(4) = $62,000.
In the table for stage 1, we actually need to obtain the optimum for xl = 4 only because this is the last stage to be considered. However, the computations for x1 = 0, 1, 2, and 3 are induded to allow carrying out sensitivity analysis. For example, what happens if the vessel capacity is 3 tons in place of 4 tons? The new optimum solution can be determined as
Remarks. The cargo-loading example represents a typical resource allocation model in which a limited resource is apportioned among a finite number of (economic) activities. The objective maximizes an associated return function. In such models, the definition of the state at each stage will be similar to the definition given for the cargo-loading model. Namely, the state at stage i is the total resource amount allocated to stages i, i + 1, ... , and n.
The nature of dynamic programming computations makes it impossible to develop a general computer code that can handle all DP problems. Perhaps this explains the persistent absence of commercial DP software.
In this section, we present a Excel-based algorithm for handling a subclass of DP problems: the single-constraint knapsack problem (file Knapsack.xls). The algorithm is not data specific and can handle problems in this category with 10 alternatives or less.
Figure 10.4 shows the starting screen of the knapsack (backward) DP model. The screen is divided into two sections: The right section (columns Q:V) is used to summarize
the output solution. In the left section (columns A:P), rows 3,4, and 6 provide the input data for the current stage, and rows 7 and down are reserved for stage computations. The input data symbols correspond to the mathematical notation in the DP model, and are self-explanatory. To fit the spreadsheet conveniently on one screen, the maximum feasible value for alternative mi at stage i is 10 (cells D6:N6).
Figure 10.5 shows the stage computations generated by the algorithm for Example 10.3-1. The computations are carried out one stage at a time, and the user provides the basic data that drive each stage. Engaging you in this manner will enhance your understanding of the computational details in DP
Starting with stage 3, and using the notation and data in Example 10.3-1, the input cells are updated as the following list shows:
Note that the feasible values of m3 are 0, 1, ... , and [W/w3] = [4/1] = 4, as in Example 10.3-1. The spreadsheet automatically tells you how many m3 values are needed and checks the validity of the values you enter by issuing self-explanatory messages in row 5: "yes," "no," and "delete." .. ,
As stage 3 data are entered and verified, the spreadsheet will "come alive" and will generate all the necessary computations of the stage (columns B through P) automatically. The value -1111111 is used to indicate that the corresponding entry is not feasible. The optimum solution (f3, m3) for the stage is given in columns 0 and P Column A provides the values of f4- Because the computations start at stage 3,f4 = 0 for all values of x3. You can leave A9:A13 blank or enter all zero values.
Now that stage 3 calculations are at hand, take the following steps to create a permanent record of the optimal solution of the current stage and to prepare the spread-sheet for next stage calculations:
Step 1. Copy the x3-values, C9:C13, and paste them in Q5:Q9 in the optimum solution summary section. Next, copy the (f3, m3)-values, 09:P13, and paste them in R5:S9. Remember that you need to paste values only, which requires selecting Paste Special from Edit menu and Values from the dialogue box.
Step 2. Copy the f3-values in R5:R9 and paste them in A9:A13 (you do not need Paste Special in this step).
Step 3. Change cell C4 to 2 and enter the new values of w2, r2, and m2 to record the data of stage 2. .
Step 2 places fi+1(xi - wimi) in column A in preparation for calculating fi(xi) at stage i (see the recursive formula for the knapsack problem in Example 10.3-1). This explains the reason for entering zero values, representing f4, in column A of stage 3 tableau,
Once stage 2 computations are available, you can prepare the screen for stage 1 in a similar manner. When stage 1 is complete, the optimum solution summary can be used to read the solution, as was explained in Example 10.3-1. Note that the organization of the output solution summary area (right section of the screen, columns Q:V) is free-formatted and you can organize its contents in any convenient manner you desire.
PROBLEM SET 10.3A
1. In Example 10.3-1, determine the optimum solution, assuming that the maximum weight capacity of the vessel is 2 tons then 5 tons.
2. Solve the cargo-loading problem of Example 10.3-1 for each of the following sets of data:
3. In the cargo-loading model of Example 10.3-1, suppose that the revenue per item includes a constant amount that is realized only if the item is chosen, as the following table shows:
Find the optimal solution using DP. (Hint: You can use the Excel file excelSetupKnapsack.xls to check your calculations.)
4. A wilderness hiker must pack three items: food, first-aid kits, and clothes. The backpack has a capacity of 3 ft3. Each unit of food takes 1 ft3. . A first-aid kit occupies V4 ft3 and each piece of cloth takes about 1/2ft3. The hiker assigns the priority weights 3,4, and 5 to food, first aid, and clothes, which means that clothes are the most valuable of the three items. From experience, the hiker must take at least one unit of each item and no more than two first-aid kits. How many of each item should the hiker take?
*5. A student must select 10 electives from four different departments, with at least one course from each department. The 10 courses are allocated to the four departments in a manner that maximizes "knowledge." The student measures knowledge on a l00-point scale and comes up with the following chart:
How should the student select the courses?
6. I have a small backyard garden that measures 10 X 20 feet. This spring I plan to plant three types of vegetables: tomatoes, green beans, and corn. The garden is organized in 10-foot ro\ys. The corn and tomatoes rows are 2 feet wide, and the beans rows are 3 feet wide. I like tomatoes the most and beans the least, and on a scale of 1 to 10, I would assign 10 to tomatoes, 7 to corn, and 3 to beans. Regardless of my preferences, my wife insists that I plant at least one row of green beans and no more than two rows of toma-toes. How many rows of each vegetable should I plant?
*7. Habitat for Humanity is a wonderful charity organization that builds homes for needy fami-lies using volunteer labor. An eligible family can chose from three home sizes: 1000, 1100, and 1200 ft2. Each size house requires a certain number of labor volunteers. The Fayetteville chapter has received five applications for the upcoming 6 months. The commit-tee in charge assigns a score to each application based on several factors. A higher score sig-nifies more need. For the next 6 months, the Fayetteville chapter can count on a maximum of 23 volunteers. The following data summarize the scores for the applications and the required number of volunteers. Which applications should the committee approve?
8. Sheriff Bassam is up for reelection in Washington county. The funds available for the campaign are about $10,000. Although the reelection committee would like to launch the campaign in all five precincts of the county, limited funds dictate otherwise. The following table lists the voting population and the amount of funds needed to launch an effective campaign in each precinct. The choice for each precinct is to receive either all allotted funds or none. How should the funds be allocated?
9. An electronic device consists of three components. The three components are in series so that the failure of one component causes the failure of the device. The reliability (probability of no failure) of the device can be improved by installing one or two standby units in each component. The following table charts the reliability, r, and the cost, c. The total capital available for the construction of the device is $10,000. How 10.3 should the device be constructed? (Hint: The objective is to maximize the reliability, r1r2r3, of the device. This means that the decomposition of the objective function is multi-plicative rather than additive.)
10. Solve the following model by DP:
(Hint: This problem is similar to Problem 9, except that the variables, yi, are continuous.)
11. Solve the following problem by DP: