School of Computing & Information Technology
CSCI251 Advanced Programming
Spring 2021
Assignment 3 (Worth 10%)
Due 11:55pm Friday in Week 13
Overview
This assignment involves a Knapsack class containing a function template to add objects of various sizes
until the knapsack is near full.
- Organize your source files sensibly taking into consideration that you are using tamplates.
- Compile your code should successfully compile into KAP using a command such as:
$ g++ -std=c++17 -Wall A3.cpp libGenerate.a -o KAP - Other than the initial command line input, the program should run without user
input. - You MUST not modify collect.h and you do not need to submit it. You are using it in developing
and testing your code.
A knapsack
Knapsack problems relate to resource allocation. In this assignment, the emphasis is not on optimization,
you will add objects as they arrive if they fit. There is a collection of classes A to G, provided in
collect.h and you will need to pass instances of them to a knapsack in the order they arrive, until the
next object cannot fit. You are to write a Knapsack class and the main() to support and demonstrate
the functionality required here. Your program should compile to KAP and run as:
./KAP size seed
• size : A positive integer. The size of the knapsack.
• seed : A positive integer. Random seed to be passed to the generate function.
1
A function generate(int) is prototyped in collect.h and defined in the library libGenerate.a.
It returns a letter (char) that identifies which object you need to try and fit into your knapsack.
You need to pass an object of that type to the knapsack using a function template/template function
defined inside Knapsack. That function template should take an object of arbitrary type and attempt
to”add it”to the knapsack. If the object fits, based on the size using sizeof, you record that object
as being included, using the name attribute of the classes. The object itself should not be stored in the
knapsack.
Once the next object to be passed cannot be added to the knapsack, you should stop generating
objects and provide two reports:
• Knapsack size, fill size, and a list of object types in the order added:
Knapsack size: …
Added object size: …
BADACEGD
• A list of object types in alphabetical order with the size of each type and the number of each
included:
A : size, 2
B : size, 1
C : size, 1
D : size, 2
E : size, 1
G : size, 1
Your reports should not reference classes that have not been added to the Knapsack and the Knapsack
should never specifically reference the A to G types in collect.h, or their sizes. The Knapsack class
should support the use of other types that contain a char accessible through a getName() member
function.
Note that the collect.h and libGenerate.a can be changed for testing, so you should not hardcode
sizes or attempt to predict the output from libGenerate.a. Some example output, based on specific
input are provided below:
$ ./KAP 180 17
Knapsack size: 180
Added object size: 177
CBDFBGAFF
A : 1, 1
B : 2, 2
C : 4, 1
D : 8, 1
F : 32, 3
G : 64, 1
$ ./KAP 113 200
Knapsack size: 113
Added object size: 98
GDBBEBC
B : 2, 3
C : 4, 1
D : 8, 1
E : 16, 1
G : 64, 1
2
Notes on submission
Submission is via Moodle.
Your code must compile on capa with the instructions you provide.
Please submit your source,(i.e. .cpp and .h) files, Readme.txt file and makefile if you
have one, in a zip file name studentID A3.zip. There should not be any directory structure
within the zip file. - Late submissions will be marked with a 25% deduction for each day, including days over the
weekend. - Submissions more than four days late will not receive marks, unless an extension has been granted.
- If you need an extension apply through SOLS, if possible before the assignment deadline.
- Academic misconduct is treated seriously. Specifically, any plagiarised work will be awarded a zero
mark and reported to the University. Be warned!