Landing : Athabascau University

COMP372 Exercise 16.2-3

By Guangya Wang in the group COMP372 Design and Analysis of Algorithms September 22, 2021 - 12:24pm

As the question describes, the order by increasing weight is the same with order by decreasing value. That means the first item ordered in this way has the biggest value per pound. By intuition, the first item must be put into the knapsack to get the largest value with a fixed load capacity. Meanwhile, pick item and put them into the knapsack by the order given in the question fulfill the requirement of "largest value with a fixed load capacity".

 

And the proof of correctness is straightforward. Assume, after picking item i, we then pick item i+2, rather than item i+1. As per the question description, weight of 1+2 is larger than i+1. Since i+2 fits the knapsack, item i+1 must fit as well. Meanwhile, value of i+2 is less than i+1. Thus, the set with i+2 skipping i+1 is not the optimal choice. Thus, we must first pick i+1, and then check if i+2 still fits the remaining capacity.

 

Running time of this algorithm is Ο(nlog(n)) considering the sorting process of item.

 

While, the traditional 0-1 knapsack problem could be solved by a dynamic programming algorithm, which is discussed in exercise 16.2-2.

Comments

These comments are moderated. Your comment will not be visible unless accepted by the content owner.

Only simple HTML formatting is allowed and any hyperlinks will be stripped away. If you need to include a URL then please simply type it so that users can copy and paste it if needed.

(Required)

(Required)


COMP372 Design and Analysis of Algorithms

COMP372 Design and Analysis of Algorithms

This is for course discussion.