CS 141 - Lab 6

Knapsack Problem

Directions

Find a partner. Solve the following programming problem in C++. When you finish, turn it in electronically, one copy per team. When you are done, you should work on Homework 4 or Programming Assignment 3.

Overview

Implement the dynamic programming solution to the 0,1 Knapsack problem. You should be writing a function

int knapsack(int maxWeight, vector<int> values,
vector<int> weights);

Details

The input will be in the following format:

Read in the number of items that will be considered (int n)
Read in the maximum weight (int maxWeight)
Read in the value and the weight for each of the n items (n iterations of int value int weight.)

Testing

Test cases can be found here. Run these using regular UNIX redirection & testing:

./lab5 < inputFile

Where inputFile will be one of these:

lab6test1.in should yield a value of 220.
lab6test2.in should yield a value of 154.