Homework 5

Write a program which runs the PTAS of 0/1 Knapsack Problem. (Due: April 19th)

•Input format:

•

8

100

0.75

90 33

61 30

50 25

33 17

29 15

23 12

15 10

13 9

• The first row means the number of items.
• The second row means the capacity.
• The third row is the error ratio.
• The first element of the fourth row means the profit and the second element means the weight of first item, and so on.