关于算法:COMP3023-23S-动态编程

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.