CS 341, Fall 2020
A. Lubiw, A. Storjohan
PROGRAMMING ASSIGNMENT 1
DUE: Wednesday, October 28, 5 PM. DO NOT COPY. ACKNOWLEDGE YOUR SOURCES. Please read http://www.student.cs.uwaterloo.ca/~cs341 for general instructions and policies.
1. [20 marks] Dynamic programming for two suitcases. In this programming assignment you will implement your algorithm for the Two Suitcases problem from Assignment 4, Ques- tion 2. Here is a reminder of the question:
Suppose you are moving for a co-op job, and want to choose which of your belongings to take. You have two suitcases. Suitcase 1 will be weighed and there is a limit of W kilos. Suitcase 2 won’t be weighed, but it has a volume limit of V . Suitcase 1 has no volume limit and suitcase 2 has no weight limit. You have n items, 1,2,…,n. Item i has weight wi ∈ N, volume vi ∈ N, and benefit bi if you take it with you. You can leave items behind.
The goal is to find the maximum benefit by choosing items for the two suitcases while ob- serving weight limit W for suitcase 1 and volume limit V for suitcase 2.
In notation, you want sets S1,S2 ⊆ {1,2,…,n} such that
1. i∈S1 wi ≤W,
2. i∈S2 vi ≤ V , and
3. B = i∈S1∪S2 bi is maximized.
Implement a dynamic programming algorithm to find the maximum benefit B and the items in each suitcase given by S1 and S2. You can write your code in C++ or Python.
Your program will be tested to see if your output produces the maximum value for B and satisfies the constraints on S1 and S2 (note that the sets need not be unique, so we will not test for an exact match). We will also check how much time your program takes, to disqualify brute-force solutions.
Input and Output. Your program should read from standard input and write to standard output. The input consists of four lines:
1. 3 whitespace delimited positive integers which are n, W and V . 2. n whitespace delimited positive integers w(i) for i = 1, 2, . . . , n. 3. n whitespace delimited positive integers v(i) for i = 1, 2, . . . , n. 4. n whitespace delimited positive integers b(i) for i = 1, 2, . . . , n.
The output contains three lines:
1. the maximum value B.
2. a list of whitespace delimited numbers indicating the items in subset S1 ⊆ {1, . . . , n}. 3. a list of whitespace delimited numbers indicating the items in subset S2 ⊆ {1, . . . , n}.
YoustillneedtoprintanemptylineifS1 =∅orS2 =∅. 1
Examples.
(a) For the following input:
2 10 40
87
20 56
3 11
the output is: 14
2 1
(b) For the following input:
555 26562 65451 46742 the output is: 13
15
3
another valid output is: 13
3
2
Submission Guidelines.
• Programming assignments are submitted through Marmoset: https://marmoset.student.cs.uwaterloo.ca/
• Your program will be compiled / run in the student Linux environment using the com- mand “g++ -std=c++14” for C++ and “python3” for Python.
• Submit one zip file containing only your code file which must be named “prog1.cpp” or “prog1.py”.
• Your score will be the score of your best submission, which depends on a set of secret testcases. You will be able to see only small testcases as a sanity check for your code.
• Finally, you can expect the input to satisfy that
– n≤106,W ≤103,V ≤103,nWV ≤108,and – wi,vi,bi ≤ 103 for i = 1,…,n.
2