COMP3023 23S Programming Assignment
Lecture 10 introduces the dynamic programming algorithm for the 0-1 knapsack problem. In
this programming assignment, you need to implement the algorithm under the following
requirements.
Environment
- The implementation must be done in standard C or C++ (using gcc/g++ compiler).
Please do not use visual studio. For the students who do not have the compiler, you can
use online GDB at https://www.onlinegdb.com/.
- The submissions which cannot pass gcc/g++ compiling, will directly receive 0. To
check whether your code can pass compiling, use online GDB at least.
Implementation Structure
In your program, you need to implement three source files “main.c”, “lib.h”, and “lib.c”
(“main.cpp”, “lib.h” and “lib.cpp” if you use C++).
For “main.c” (or “main.cpp”)
- It only contains the “main” function.
- It reads inputs from .txt files. The input txt file is passed to the main function as an
argument.
- Each txt file contains exactly one instance.
For “lib.h” and “lib.c” (or “lib.h” and “lib.cpp”)
- .h is the header file for .c (or .cpp).
- They contain all other functions except “main”.
Functionality
- The input txt file has 3 lines. The first line has only one integer, the capacity of the bag.
The second line has a bunch of positive integers for the value of each item. Two integers
are separated by a comma “,”. The third line is in the same format as the second for the
weight of each item.
- When the calculation is finished, print the optimal value and optimal solution(s) one
for each line on the screen. (The optimal value is unique, but the optimal solution may
not.)
- Sort the items in the optimal solution(s) in the decreasing order of item indices.
- The index of items starts from 1.
Sample:
In the folder “Sample”, you will find all the source files described above. Take the C version
in subfolder “c” for example (the C++ version is in subfolder “c++”). Currently, all source files
are empty. The main function simple prints the argument on the screen. “lib.c” only tests the
linkage. The package also contains “make.bat”. You can open it by a TXT editor. Then, you
can see the compilation commands.
After executing “make.bat” (Note that .bat files are only executable in Windows), you will have
“knapsack.exe”.
Suppose the input txt file is named as “in.txt”, we execute “knapsack in.txt”.
We see that “in.txt” is printed and “lib.h” and “lib.c” are tested.
Example instance
Suppose the input file (in1.txt) contains
10
3,5,2,6
3,4,2,5
When you finished, the output should be something like
Because
𝑤4 + 𝑤3 + 𝑤1 = 5 + 2 + 3 = 10 ≤ 𝑊
𝑣4 + 𝑣3 + 𝑣1 = 6 + 2 + 3 = 11
And
𝑤4 + 𝑤2 = 9 ≤ 𝑊
𝑣4 + 𝑣2 = 11
Submission requirements
You need to submit three source files “main.c”, “lib.h”, and “lib.c” (“main.cpp”, “lib.h” and
“lib.cpp” if you use C++) separately to iSpace.