Items have weights and values (where ), respectively. The problem of packing items into a knapsack with a maximum weight capacity such that the total value is as large as possible is called the knapsack problem, which can generally be formulated as follows.
[Problem A0]
Maximize
Subject to , ( when item is packed into the knapsack)
As a specific knapsack problem, consider the following [Problem A1].
[Problem A1]
Maximize
Subject to
The most direct solution method is the enumeration method, where all cases are generated and examined. In the specific example of [Problem A1], the number of cases is well within the calculable range, but as the number of items increases, the number of cases increases exponentially. Therefore, here we consider efficient search using two methods: (1) the branch and bound method and (2) dynamic programming.
(1) Search by the branch and bound method
(1-1) Explain the operation of the branch and bound method for maximizing an objective function using the following terms: "branching operation," "subproblem (child problem)," "tentative value," "upper bound," "bounding operation," and "feasible solution."
(1-2) In the case of the knapsack problem, it is convenient if the items are sorted in the order of value per unit weight; in [Problem A1] above, the value per unit weight is higher in the order . By relaxing the condition and setting , the solution to the relaxed problem can be easily found in this case. When , a maximum value of can be obtained. This estimate gives an upper bound on the total value for the condition . This calculation of the upper bound by the relaxation problem can be similarly utilized for subproblems.
For [Problem A1], find the solution by performing a branch and bound search in a vertical (depth-first) search that instantiates in that order, and in the order of values .
Show the search tree, the items packed in the knapsack , and the maximum total value in your answer.
(2) Calculation by dynamic programming
Consider finding the solution to the same knapsack problem using dynamic programming. Here, without loss of generality, let and in the generalized [Problem A0] be positive integers. Then, define the following function (where and are integers such that ).
: the maximum total value obtained when candidates for items to be packed within a weight limit are limited to .
Clearly is , and for [Problem A1], and . Then, the final maximum total value for [Problem A1] is found as , and the final maximum total value for [Problem A0] will be found as .
(2-1) Starting from this or , we want to obtain a method to finally calculate while sequentially increasing in the general [Problem A0]. If (where ) has been found, show the method to find using this as a formula. However, if is a negative integer, it is permissible to obtain the formula by setting for convenience.
(2-2) Using the above results, solve [Problem A1] by sequentially calculating the table for shown below for [Problem A1].
Show the table for with calculated numerical values, the items packed in the knapsack, and the maximum total value in your answer.