Goods have their weights and value (), respectively. The problem of packing the maximum total value of goods into a knapsack with a weight limit is called the knapsack problem, which can be generally formulated as
[Problem A0]
Here, we specifically consider the following knapsack problem [Problem A1].
[Problem A1]
The most straightforward approach to this problem is the enumeration method, in which all the cases are generated and evaluated. Although the number of possible cases in [Problem A1] is and fully within a computable range, this number grows exponentially as the number of possible goods increases. Then, we here try to achieve efficient searches through two methods, namely, (1) the branch and bound method and (2) dynamic programming.
(1) Search by the branch and bound method
(1-1) Explain the behavior of the branch and bound method maximizing an objective function, using the following terms:
"branching operation", "sub-problems (child problems)", "incumbent value", "upper bound value", "bounding operation", and "feasible solution"
(1-2) In the knapsack problems, it is convenient if the goods are sorted according to the values per unit weight. In [Problem A1], are sorted to have higher values per unit weight in this order. A solution of this relaxed problem, where the constraint is relaxed to , can be easily obtained with the maximum value when . This estimate gives an upper bound of the total value for the original knapsack problem with . Upper bound calculation by employing such relaxed problems can be used also for sub-problems.
In a depth-first search instantiating to and in this order for [Problem A1], execute a search based on the above branch and bound method to find the solution.
Show the resultant search tree, the goods to be packed into the knapsack and the maximum total value obtained.
(2) Computation by dynamic programming
We consider here to solve the same knapsack problem by employing dynamic programming. Without a loss of generality, we assume here that and in the general problem of [Problem A0] are positive integers. Then we define the following function where and are integers with and .
: The maximum total value when limiting the candidates of the goods to which can be packed into the knapsack under the maximum weight constraint .
Apparently, is 0, and in [Problem A1], and . Eventually, the final answer of the maximum total value for [Problem A1] can be obtained as , and the final answer for [Problem A0] can be obtained as .
(2-1) Starting from these or , we want to get a method of eventually calculating for the general problem of [Problem A0] by incrementing in sequence. When where are calculated, show a method of calculating as an equation using these . Here, you can show the equation for convenience by letting when is a negative integer.
(2-2) Using the result of the above question, solve [Problem A1] by calculating cell values of the table shown below in sequence. Show the table with the calculated values , goods to be packed into the knapsack, and the maximum total value.