Knapsack Example

The Knapsack Problem is a simple abstraction of decision-making subject to resource constraints. The problem is to select items to maximize their total value without exceeding a limitation on total resource. Each item type is characterized by its unit value and resource consumption. Multiple units of each item type may be selected.

Problem Description

The problem we will consider here involves four kinds of items:

Item	Value	Resource
1	30	10.7
2	18	6.9
3	16	6
4	7	3

The total available resource is 37.

In Hava, these problem parameters take the following form:

struct Item(val, res);
table Items = collect(Item(30, 10.7), Item(18, 6.9), Item(16, 6), Item(7, 3));
N = Items.listSize;
R = 37;

Enumeration Algorithm

The steps in an enumeration algorithm are:

Generate a list of all feasible assignments.
Select the assignment that has the largest total value.

The trouble with enumeration is that the number of feasible assignments can become quite large. For problems involving only a few item types, however, enumeration is a convenient and conceptually easy way to solve the problem.

Let us start by considering item i alone. Each unit requires Items[i].resource, and the quantity selected must be a whole number. Given the resource capacity R, the maximum quantity that can be selected is floor(R/Items[i].res). The list of possible allocation quantities of item i is therefore:

K(i) = 0 to floor(R/Items[i].res).

In our example, K(1) = (0, 1, 2, 3), K(2) = (0, 1, 2, 3, 4, 5), etc.

We shall construct the list of feasible assignments recursively, starting with a single item type, and building up to the given list of four. Let A(i) be the list of feasible allocations of the first i items. Clearly, A(1) = K(1). For i>1, A(i) is determined from A(i-1) and K(i), by considering every allocation a₁…a_i where a₁…a_i-1 is in A(i-1) and a_i is in K(i), and retaining only those that satisfy the resource constraint. In Hava, this is written as:

A(i) = if (i == 1) {K(1)} else {Merge(A(i-1), K(i))};
function Merge(A, K) = collect(a in A, k in K, m=join(a, k) | r(m) <= R) {m};
function r(a) = sum(i = 1 to a.listSize) {a[i]*Items[i].res};

The enumeration may now be simply stated:

optAlloc = argmax(a in A(N)) {v(a)}; 
function v(a) = sum(i=1 to a.listSize) {a[i]*Items[i].val};

Click here to view the complete solution by enumeration.

Solution by Dynamic Programming

Suppose that the decision-maker has already selected allocations for items 1 … i-1. The basis for selecting the remaining items, also known as the decision-maker's state, is (i, r), where i is the index of the next item to be allocated, and r is the amount of resource remaining. Let optValue(i, r) denote the optimal value of the remaining allocations, when in state (i, r).

If k is the next allocation selected, when in state (i, r), the value of this allocation will be k*Items[i].val. Furthermore, the decision-maker will next enter state (i+1, r - k*Items[i].res). The optimal value of the remaining allocations will be optValue(i+1, r - k*Items[i].res). Thus, optValue(i, r) is the maximum, over allowable k, of:

function V(i, r, k) = k*Items[i].val + optValue(i+1, r - k*Items[i].res);

But the set of allowable k, when in state (i, r), is simply

K(i, r) = 0 to floor(r/Items[i].res);

Conveniently, the two previous definitions happen to fit the form of Hava statements! It remains only to put the recursion together to form:

optValue(i, r) = 
  if (i > N) {0}
  else {max(k in K(i, r)) {V(i, r, k)}};

Hava can solve the problem from here. To kick it off, we have only to request

SOLUTION = optValue(1, R).

But that would only show the optimal value, not the optimal allocation. To find the latter, we need to "rewind", in the manner characteristic of dynamic programming. The details are shown in the code sample.

Click here to view the complete solution by dynamic programming.

Extension

Can you modify the Hava solution to accommodate a second type of resource?