Knapsack Problem

The Unbounded Knapsack Problem

If you have never heard about this problem (shame on you!) you might be interested in taking a quick look at the formal definition given below. The name derives from the following interpretation: suppose that you have a knapsack of volume U and you wish to fill it up with available items so as to maximize the total value of the items in the knapsack. What items should be selected?

There are several versions to this problem related to the availability of items. In particular, the 0-1 version represents a situation where only one item of each type is available or can be selected. The unbounded case, which we consider here assumes that there are n types of items and that there are ifinitely many items of each type. The raw input data for this version consists then of the following:

The JavaScript code used here is a naive implementation of the dynamic programming functional equation described below.


Item, i NicknameValue, viVolume, uix*i
U = z(U) =

So here is the formal picture:

z(U):= max { v1x1 + v2x2 + ... + vnxn}

subject to:

u1x1 + u2x2 + ... + unxn <= U

x1,...,xn are non-negative integers

The volumes u1,...,un of the items as well as the total volume of the knapsack, U, are assumed to be non-negative integers.

Recall that, as indicated above, the "unbounded" version of the knapsack problem allows you to select as many items of each type as you wish, subject to the total volume constraint.

The JavaScript code is a naive implementation of the following famous dynamic programming functional equation:

z(s) = max { vi + z(s - ui) : i = 1,2,...,n, ui<=s} , u* <= s <=U

z(s) = 0 , s < u*:= min {ui: i=1,2,...,n}

In the report we denote by d*(s) the optimal decision (item) generated by solving the functional equation for a given s. The recovery procedure simply implement the strategy prescribed by d* starting with s=U and terminating when s<=u*.