COMP3023 Design and Analysis of Algorithms - Programming Assignment: 0-1 Knapsack Problem
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 optim al 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 t he 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 t hat .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 Suppo se the input file (in1.txt ) contains 10 3,5,2,6 3,4,2,5
When you finished, t he 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 .
