Questions on further packing and the knapsack problem

Question 1

State what a knapsack problem asks for, and say how it differs from a bin packing problem.

Accepted Answer

Each item has a mass and a profit and the container has a mass limit; the problem asks which items to load so that the total mass stays inside the limit and the total profit is as large as possible. B1. Bin packing takes the whole list of items and minimises the number of bins, while a knapsack has one container and leaves items behind, so the decision is which items to take rather than where to put them. B1.

Question 2

A van carries 12 kg. The crates are R at 4 kg for £36, S at 5 kg for £42, T at 7 kg for £56 and V at 8 kg for £60. Rank the crates by profit per kilogram and load the van by that ranking.

Accepted Answer

Profit per kilogram: R gives 36 ÷ 4 = £9.00, S gives 42 ÷ 5 = £8.40, T gives 56 ÷ 7 = £8.00 and V gives 60 ÷ 8 = £7.50, so the ranking is R, S, T, V. R goes in at 4 kg, then S takes the load to 9 kg. T would carry it to 16 kg and V to 17 kg, so neither fits. The load is R and S, 9 kg, £78. M1 for the four densities, A1 for the ranking, A1 for the load and its value. Show every division: a ranking has to be justified by the ratios themselves.

Question 3

A bag carries 9 kg. The items are F at 4 kg for £24, G at 6 kg for £30 and H at 5 kg for £20. Allowing items to be split, find the greatest profit the bag can carry, and state what that figure establishes about the best load of whole items.

Accepted Answer

Profit per kilogram: F gives 24 ÷ 4 = £6.00, G gives 30 ÷ 6 = £5.00 and H gives 20 ÷ 5 = £4.00, so load in the order F, G, H. M1 for the three densities. All of F takes 4 kg and earns £24. That leaves 5 kg, which takes five sixths of G at £5.00 per kg for a further £25, and the bag is full. The greatest profit with splitting allowed is 24 + 25 = £49. A1. Allowing splits can only add options, so no whole-item load can beat £49: the figure is an upper bound on the best whole-item load, not a load that can be achieved. B1.

Question 4

State the one version of the knapsack problem for which loading in order of profit per unit mass is certain to give the best answer, and say why the whole-item version escapes it.

Accepted Answer

It is certain to be best when items may be split, so that any fraction of an item may be loaded: the rule then fills the container with the most profitable kilograms available, and every kilogram of the limit is used. B1.
With whole items the rule must pass over anything that will not fit and can leave part of the limit unused, when a heavier item already turned down would have filled that gap for more profit. B1.

Question 5

For the van in question A2, show that the greedy load is not the best, state the best load, and explain in one sentence why the ranking misled you.

Accepted Answer

Working through the loads that fit: S with T is 12 kg for £98, R with V is 12 kg for £96, R with T is 11 kg for £92, and R with S is the £78 already found.
So the best load is S and T, filling the van, worth £98, and the greedy rule fell £20 short.
The ranking put R first because it pays best per kilogram, but the 4 kg it took were the room T needed, and T is worth £56 on its own. A rule that judges one crate at a time cannot see that. M1 for testing loads other than the greedy one, A1 for £98, A1 for naming S and T, B1 for the explanation.

Question 6

Formulate the van problem of question A2 as an integer programme.

Accepted Answer

Let x₁, x₂, x₃, x₄ be 1 when R, S, T, V respectively are loaded and 0 when they are left behind.
Maximise P = 36x₁ + 42x₂ + 56x₃ + 60x₄
subject to 4x₁ + 5x₂ + 7x₃ + 8x₄ ≤ 12,
with each x_i equal to 0 or 1. B1 for defining the variables as nought-or-one, B1 for the objective, B1 for the constraint together with the integer condition.

Question 7

A bag carries 7 kg. The items are X at 2 kg for £14, Y at 3 kg for £19 and Z at 4 kg for £26. Build the dynamic programming table for limits 0 to 7 kg and use it to name the best load.

Accepted Answer

Each cell is the best profit from the items listed so far under the limit at the head of its column: leave the new item and copy the cell above, or load it and add its profit to the cell above it that is lighter by its mass.
Limits 0 to 7 across the top.
X: 0, 0, 14, 14, 14, 14, 14, 14.
X Y: 0, 0, 14, 19, 19, 33, 33, 33.
X Y Z: 0, 0, 14, 19, 26, 33, 40, 45.
Reading back up the last column: 45 differs from the 33 above it, so Z was loaded and the limit falls by 4 to 3. There 19 differs from the 14 above it, so Y was loaded and the limit falls to 0, where X was not.
The best load is Y and Z, 7 kg, £45. M1 for a correct first row, M1 for the recurrence in use, A1 for the completed table, M1 for the trace back, A1 for the load.
The greedy rule would have taken X first, for a density of £7.00 per kg, and finished on £40. Naming the items is part of the answer: a table ending in 45 with no trace back is incomplete.

Question 8

A van carries 12 kg. The crates are R at 4 kg for £36, S at 5 kg for £42, T at 7 kg for £56 and V at 8 kg for £60, and the best whole-crate load is known to be worth £98. Load the van by profit alone rather than by profit per kilogram. Then allow crates to be split and load in profit-per-kilogram order to obtain an upper bound, and explain what the bound does and does not tell you about the £98.

Accepted Answer

By profit the ranking is V at £60, T at £56, S at £42 and R at £36. V goes in at 8 kg; T would take the load to 15 kg and S to 13 kg, so both are refused; R completes the load at 12 kg. This rule earns V and R, 12 kg, £96, £2 short of the best, so it beats loading by profit per kilogram here and still falls short.
Now allow splitting and load in density order: all of R at £9.00 per kg is 4 kg for £36, all of S at £8.40 takes the load to 9 kg for £42 more, and the last 3 kg take three sevenths of T at £8.00 per kg for £24. The ceiling is 36 + 42 + 24 = £102.
Splitting can only widen the choice, so no whole-crate load can beat £102: the bound certifies that nothing better than £102 exists, and so confirms the £98 load is within £4 of anything possible. It does not name the best load, and it does not say whether £102 is reachable in whole crates; here it is not. M1 for loading in profit order with the refusals shown, A1 for V and R at £96, M1 for the fractional load in density order, A1 for the ceiling £102, B1 for what the bound does and does not establish.

Question 9

A lorry rated at 1000 kg is to be loaded from 20 crates whose masses are whole numbers of kilograms. Compare the number of subsets a complete search would check with the number of cells in the dynamic programming table, and explain what happens to each count if the same lorry is rated at 1 000 000 g instead.

Accepted Answer

A complete search checks every subset of the 20 crates: 2²⁰ = 1 048 576 subsets. The table has a row for each crate and a column for each whole-kilogram limit from 0 to 1000, so 20 × 1001 = 20 020 cells, each filled by one comparison: the table is smaller by a factor of about fifty.
Rated in grams the crates and the possible loads are unchanged, so the count of subsets stays at 1 048 576. But the table now needs a column for every whole-gram limit from 0 to 1 000 000, so 20 × 1 000 001 = 20 000 020 cells, and the advantage reverses.
The table's work grows as the number of items times the size of the limit rather than as 2ⁿ, so the method is quick in the number of items and slow in the size of the limit, and the size of the limit depends on the unit it is written in. B1 for the 1 048 576 subsets, B1 for the 20 020 cells, B1 for the comparison in kilograms, B1 for the reversal in grams with the reason.

Question 10

A van carries 9 kg. The items are F at 3 kg for £21, G at 4 kg for £26 and H at 5 kg for £34. Build the dynamic programming table for limits 0 to 9 kg, use it to name the best load, and compare that load with the one profit per kilogram would have given.

Accepted Answer

Each cell holds the best profit from the items listed so far under the limit at the head of its column: either leave the new item and copy the cell above, or load it and add its profit to the cell above that is lighter by its mass.
Limits 0 to 9 across the top.
F: 0, 0, 0, 21, 21, 21, 21, 21, 21, 21.
F G: 0, 0, 0, 21, 26, 26, 26, 47, 47, 47.
F G H: 0, 0, 0, 21, 26, 34, 34, 47, 55, 60.
M1 for a correct first row, M1 for the recurrence in use, A1 for the completed table.
Reading back up the last column: 60 differs from the 47 above it, so H was loaded and the limit falls by 5 to 4. There 26 differs from the 21 above it, so G was loaded and the limit falls to 0, where F was not. The best load is G and H, 9 kg, £60. M1 for the trace back, A1 for the load.
Profit per kilogram is F £7.00, H £6.80 and G £6.50, so that rule loads F first, then H, reaching 8 kg for £55 with G left behind and a kilogram to spare: £5 short of the table's load. B1 for the greedy load and the comparison.

Question 11

Five rectangles are to be cut from a roll 8 units wide, without being turned: J 5 by 4, K 3 by 4, L 4 by 3, N 4 by 3 and P 2 by 2, width given first. Pack them by shelves of decreasing height, state the length used, and find the area lower bound.

Accepted Answer

Sorted by decreasing height: J and K at 4, then L and N at 3, then P at 2.
Shelf 1 takes J (5 wide) and K (3), which fill the width exactly, and is 4 high. Shelf 2 takes L and N, 4 wide each, filling the width again, and is 3 high. Shelf 3 holds P alone, is 2 high, and leaves 6 units of width empty. M1 for the shelves in decreasing height order.
Length used = 4 + 3 + 2 = 9. A1.
The pieces cover 20 + 12 + 12 + 12 + 4 = 60 square units on a roll 8 wide, so no packing can be shorter than 60 ÷ 8 = 7.5. M1 for the total area over the width, A1 for 7.5.
The shelf packing wastes 9 × 8 − 60 = 12 square units, all of it beside P on the last shelf, so it does not meet the bound and nothing here says whether 7.5 is reachable.

Question 12

Six rectangles are to be cut from a roll 10 units wide, without being turned: A 4 by 6, B 3 by 6, C 3 by 4, D 5 by 4, E 5 by 4 and F 3 by 2, width given first. Pack them by shelves of decreasing height, find the area lower bound, and then find a packing that meets the bound.

Accepted Answer

Sorted by decreasing height: A and B at 6, then C, D and E at 4, then F at 2.
Shelf 1 takes A (4), B (3) and C (3), which fill the width; D would need 5 more. Its height is 6, set by A and B, so C leaves a gap 3 wide and 2 high above it.
Shelf 2 takes D and E, filling the width again, and is 4 high. Shelf 3 holds F alone, is 2 high, and leaves 7 units of width empty. The length used is 6 + 4 + 2 = 12.
Area bound: the pieces cover 24 + 18 + 12 + 20 + 20 + 6 = 100 square units on a roll 10 wide, so no packing gets below 100 ÷ 10 = 10.
Now put F in the gap above C. A, B and C along the bottom with F resting on C fill a band 6 high; D and E fill a band 4 high above them; the roll stops at 10 with nothing wasted.
That packing meets the bound, so 10 is optimal and no further argument is needed. M1 A1 for the shelves, A1 for the height of 12, M1 A1 for the area bound, M1 A1 for a packing of height 10, B1 for saying the bound settles it.
The shelf rule lost 2 units because a shelf's height is fixed by its tallest piece and F arrived after both earlier shelves had closed.

Question 13

A container has a base 6 units by 4 and is open at the top. Six boxes are to be stacked in it without being turned: J with base 6 by 4 and height 2, K and L each with base 3 by 4 and height 3, M with base 6 by 2 and height 2, and N and P each with base 3 by 2 and height 2. Find a lower bound for the height of the stack, and find a stacking that meets it.

Accepted Answer

The bound comes from volume, as the area bound did in two dimensions. The volumes are J 6 × 4 × 2 = 48, K and L 3 × 4 × 3 = 36 each, M 6 × 2 × 2 = 24, and N and P 3 × 2 × 2 = 12 each, totalling 168. The base holds 6 × 4 = 24 square units, so each unit of height holds at most 24 of volume, and the stack is at least 168 ÷ 24 = 7 high. The height of the tallest box is another lower bound, but at 3 it is below 7, so the volume bound is the binding one.
Now build the stack in layers that each fill the base exactly. J alone covers 6 by 4: a layer of height 2. K beside L gives 3 + 3 by 4: a layer of height 3. M covers 6 by 2 and N beside P cover the remaining 6 by 2: a layer of height 2.
The heights add to 2 + 3 + 2 = 7, which meets the bound, so 7 is optimal and no further argument is needed. M1 for the six volumes and their total, A1 for the bound of 7, B1 for checking the tallest box against it, M1 for layers that fill the base, A1 for the completed stack of height 7, A1 for concluding from the bound that 7 is optimal.

Question 14

A bag carries 10 kg. The items are R at 3 kg for £27, S at 4 kg for £34, T at 6 kg for £48 and V at 7 kg for £54. Load the bag by profit per kilogram, then by profit alone, then find the best load of whole items, and finally find the upper bound obtained by allowing items to be split. State what the four figures together establish.

Accepted Answer

Profit per kilogram: R 27 ÷ 3 = £9.00, S 34 ÷ 4 = £8.50, T 48 ÷ 6 = £8.00, V 54 ÷ 7 = £7.71. M1 for the four densities. By density: R goes in at 3 kg, S takes the load to 7 kg, then T would take it to 13 kg and V to 14 kg, so neither fits. Load R and S, 7 kg, £61, with 3 kg unused. A1. By profit the ranking is V £54, T £48, S £34, R £27. V goes in at 7 kg; T and S will not fit; R completes the load at 10 kg. Load V and R, 10 kg, £81. A1. Testing the loads that fit: S with T is 10 kg for £82, V with R is £81, T with R is 9 kg for £75, S with R is £61 and V alone is £54. The best load is S and T, filling the bag, worth £82. M1 for testing the subsets, A1 for £82 with S and T. Splitting, and loading in density order: all of R for £27, all of S taking the load to 7 kg for £34 more, then 3 kg of T at £8.00 per kg for £24. The ceiling is 27 + 34 + 24 = £85. M1 A1. Together: £82 is achievable because a load worth it has been written down, and nothing whatever can beat £85. Neither greedy rule found the best load, and the two rules disagree with each other by £20, so a load produced by either needs checking before it is accepted.

Question 15

A knapsack carries 10 kg and the items are X (5 kg, £10), Y (5 kg, £10) and Z (10 kg, £21). Find the best load. Every mass and the limit are then doubled: explain why the best load does not change. Instead, £2 is added to the profit of every item, the masses being unchanged: find the new best load and explain why adding the same amount to every profit can change the answer.

Accepted Answer

The loads that fit are X alone (£10), Y alone (£10), X with Y (10 kg, £20) and Z alone (10 kg, £21). The best is Z alone, £21. B1.
Doubling every mass and the limit multiplies both sides of the constraint by 2, so a set of items fits the 20 kg bag exactly when it fitted the 10 kg one: X with Y is now 20 kg against a 20 kg limit, and Z is 20 kg as well. The profits are untouched, so the same comparison is made between the same loads and the answer is still Z. M1 for the loads that fit being unchanged, A1 for the conclusion.
Adding £2 to each profit gives X £12, Y £12 and Z £23. Now X with Y is worth £24 against Z's £23, so the best load becomes X and Y, £24. M1 for the new comparison, A1 for X and Y at £24.