Written in C++

Here is what I have on the slides for the Algorithim:

The Knapsack Problem

A lot like subset sum, but each item has a value in addition to a weight.

Value vector {v1, v2, ... , vn}

We want to maximize value, while not exceeding maximum weight. Some items might be proportionately more valuable than others.

Each cell = OPT(i,w) if w< wi then OPT(i,w) = OPT(i-1,w) else OPT(i,w) = MAX(OPT(i-1,w), vi + OPT(i-1, w- wi )

Description: You are to implement the O(nW) matrix based dynamic programming algorithm to solve the Knapsack problem.

I/O Specifications: You will read your input instance from an input file named knapsack.txt of the following format: The first line will specify the number of items n and the weight bound W. Every following line k will specify the weight of item k and the value of item k (separated by a space). A sample input corresponding to slide 28 is as follows:

46 24 15 21 32

Output will give both the total value of the optimal Knapsack solution, and the subset of items involved in the optimal Knapsack solution. Output will be to console. E.g., the output for the example above is:

The optimal Knapsack solution has total value 11 and involves items {1, 2, 4}.

Algorithmic Specifications: The dynamic programming algorithm is exactly as described in the slides 13Dynamic programming.pptx and the Dynamic Programming chapter of the text. It is based on constructing the n by W matrix of all optimal subproblems, where each enty

(r,c) depends only on the entries (r-1,c) and (r-1,c-wr). Including a zeroth row and zeroth column is also convenient, and those should be initialized to zero as well. Observe that the

overall time complexity of O(nW) is not actually polynomial time.