联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2023-05-13 04:23

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.


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp