CPS616

W2017 Lab 7

Ryerson University

Worth: 6%

Dynamic Programming Knapsack

Due: Wednesday April 5


Team size

This lab can be done in teams of 1 or 2.

Lab Description

In this lab you will implement two improvements to a backtracking knapsack solution:
  • The improvement suggeted in lab6
  • Turning the algorithm into a dynamic programming "Memory function" version
You will be timing these improvements.

Background

Here is the Javadoc for a Java implementation of the pseudocode knapsack algorithm in lab6.

Lab

In this lab you will have three versions of the knapsack problem: the one provided to you, and the two changes you will make. Keep these three versions as you are asked to time them and compare them.
  1. Modify the Solution class to implement the small improvement suggested in the pseudocode knapsack algorithm in lab6. Note that you do not need to change any class other than Solution, and you will not need to change the Solution API either: Problem.bestFit() will still call Solution.getWorth(), but getWorth() should not loop through the items.
  2. Modify Problem.bestFit to implement the dynamic programming "Memory function" (see pages 5-6) version of the knapsack problem solution.
  3. Modify Test.java to be able to time the three versions of the solutions, just like you did for Assignment: generate randomly knapsack problems of increasing size and record average speads for each size. However, this time, you should not double n (= number of items) at each step as you did for the assignment. Instead you should just increase n by 10 until your computer can't handle the testing any more. Note that because you are changing n in a linear fashion, you should be able to collect all your times for each of the three versions of knapsack all at once in one run, and therefore you will only need to run the testing 3 times (on the same machine), once for each version of the knapsack solution.
  4. Plot your results for the three versions in matlab using a linearly scaled x axis and a log scaled y axis. Also plot 2n.
  5. Answer the question on the lab7 marking sheet (docx or pdf)

Notes on Java Implementation

As you implement dynamic programming in Java, there are a few things to keep in mind about storing partial solutions in a table.
  • When your algorithm decides to retrieve a partial Solution that was stored in the dynamic programming table, and to store a modified modify of it as a separate entry in the table it should modify a copy of this Solution and not the original Solution because otherwise this will damage the original results in the table. This is accomplished by making the Solution class cloneable.
  • The Solution.clone() method should perform a deeper cloning of the Item[] field, which is an array, to make sure that the array in the clone is different from the array in the original Solution. Otherwise adding items to this array would also invalidate the results. The actual Items in the array, however, do not need to be cloned as they are never modified.

Additional Material

Hand In

  • This lab will be graded on the moons and should therefore be submitted on the moons. Please submit a zip file containing your three revised java classes: Test.java, Problem.java, and Solution.java. Only submit your last version: it incorporates all the changes you have made. You will be partially graded by a script so do not rename your classes or change the APIs of your classes. The only exception is for making Solution cloneable. We will have two tests: one for Solution being cloneable fot the solutions that rely on this, and one where it is not to test the solutions that used an alternative approach to copying objects.
  • Also hand in a printout of your marking sheet (docx or pdf) so that we know where to find your submission and staple a copy of the plot to this sheet.
  • In addition to the lab itself you will need to also submit the Lab Submission Declaration on D2L. This lab will not be graded unless this declaration has been submitted


This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Tuesday, 04-Apr-2017 15:33:28 EDT