# CS计算机代考程序代写 compiler Hive CS211 Spring 2021 Programming Assignment II

CS211 Spring 2021 Programming Assignment II
David Menendez
Due: March 12, 2021, 10:00 PM Hand in by March 13, 2021, 4:00 AM
1 Background: the knapsack problem
We have a set of items, each of which has a weight and a value. We want to pack these items into a knapsack, but there is a maximum amount of weight that the knapsack can carry. Our goal is to find the most valuable subset of the items whose total weight does not exceed the knapsack’s weight limit.
For simplicity, we assume that the weights and values for each item are positive integers. We also assume that the knapsack can carry any combination of items, as long as the weight limit is not exceeded.
For example, we might have five light items with weight 1 and value 10, and one heavy item with weight 4 and value 39. If our knapsack’s weight limit is 6, what is the maximum total value of the items we can place in the knapsack?
1.1 Formal definition
An instance of the knapsack problem involves a weight limit L and N items, numbered from 0 to N − 1. Each item i has a weight wi and value vi.
A solution to the knapsack problem is a set if items S that maximizes the total value
􏰁vi (1)
such that
1.2 Non-optimal approaches
i∈S
􏰁wi ≤L. (2) i∈S
A naïve strategy is to test every combination of items and keep the combination with the highest total value of all combinations that do not exceed the weight limit. This strategy requires checking 2N subsets o items, leaving it impractical for all but the smallest problems.
A greedy approach might sort the items by some metric, such as value or ratio of value to weight, and repeatedly choose the best item that does not exceed the remaining weight limit. Unfortunately, this approach is not guaranteed to find an optimal subset.
1

Going back to our example, if our weight limit is 5 and we choose the most valuable items first, we will select the heavy item and one light item, for a total value of 49. The optimal subset with total weight 5 is to take five light items, for a total value of 50.
If we choose items to maximize value per weight, we will find the optimal set for weight limit 5. If the weight limit is 6, we will chose five light items again, for a total value of 50. Here, the optimal solution is to choose two light items and the heavy item, for a total value of 59.
1.3 Method: Dynamic programming
We will use a dynamic programming approach to find optimal solutions. Dynamic programming finds a solution to a problem by first finding solutions to smaller sub-problems.
For our knapsack problem, we will write Vln to indicate the maximum total value obtainable with items 0 through n subject to weight limit l. Thus, V N−1 is the maximum value obtainable
L
We will construct a table containing V n for all subproblems from V 0 to V N−1. To simplify the
using all N items with weight limit L.