CSCI251 Advanced Programming - Assignment 3: Knapsack
School of Computing & Information Technology
CSCI251 Advanced Programming Spring 2023
Assignment 3 (Worth 8%)
Due 11:55pm Friday in Week 13 (27th Oct,2023)
Overview
This assignment involves a Knapsack class containing a function template to add objects of various sizes until the knapsack is near full.
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 demonstrate the functionality required here. Your program should compile to KAP and run as:
./KAP size seed durability
• size : A positive integer. The size of the knapsack.
• seed:Apositiveinteger.Randomseedtobepassedtothegeneratefunction.
• durability: A positive integer. The maximum number of resets the knapsack can execute.
1
A function generate(int) is prototyped in collect.h and defined in the library libKnap.a.
It returns a letter (char) that identifies which object you need to try and fit into your knapsack. The
generated letter can be A to G and R and S. The letters R and S are for special classes which trigger
special condition 2 and 3. The special conditions will be described shortly.
You need to define a function template inside Knapsack and pass an object of that type to the knapsack using the function template. That function template should take an object of arbitrary type as input (i.e., generic to objects of different types) and attempt to ”add it” to the knapsack. Note that the function template is allowed to take more than one input parameter if necessary. However, only one single parameter related to the object (i.e., the object itself) is allowed.
If the object fits, based on the size using the built-in function 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, which means that the actual object information is not stored. However, it takes some space of the knapsack which is equal to the returned value of sizeof(this object). When one of the following conditions occurs, you need to output a conditioned message based on the condition we meet and then a summary report. The summary report and conditions with corresponding conditioned messages are described as below:
Summary report: It consists of two parts separated with “=======================”:
-
Knapsacksize,fillsize,andalistofobjecttypesintheorderadded.Forinstance: ==========================
Knapsack size:
Added object size: ...BADACEGD
-
Information of objects in the knapsack based on the alphabetical order, with the size of each type and the number of each included. For instance:The program produces a conditioned message followed by a summary report. After that, the Knapsack is reset, and all the previously stored objects are removed. If reaching the maximum number of resets, the process will be terminated. For instance, if the current reset is 4 and the durability is 10, the conditioned message is as below: “Condition 2: Attempt to add an R object
which triggers a reset. The number of used resets: 4 out of 10”
Condition 3 (Attempt to add an S object)
The program displays a conditioned message followed by a summary report, then stops the adding process. The conditioned message is below: “Condition 3: Attempt to add an S object which triggers early termination.”
Notice and Example outputs
Notice: The three conditions above are mutually exclusive; conditions 2 and 3 can be triggered without considering the size of R and S objects, and R and S objects cannot be added into the Knapsack; Objects not included in the knapsack should not appear in the summary report; The collect.h and libKnap.a can be changed for our marking, so you should not hardcode sizes or attempt to predict the output from libKnap.a.
Below are some examples. Note that if you test your code on Capa, you should produce the same output given the same input.
Example 1
Example 2
