Guangya Wang recommended this September 22, 2021 - 3:55pm
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.
The Landing is a social site for Athabasca University staff, students and invited guests. It is a space where they can share, communicate and connect with anyone or everyone.
Unless you are logged in, you will only be able to see the fraction of posts on the site that have been made public. Right now you are not logged in.
If you have an Athabasca University login ID, use your standard username and password to access this site.
We welcome comments on public posts from members of the public. Please note, however, that all comments made on public posts must be moderated by their owners before they become visible on the site. The owner of the post (and no one else) has to do that.
If you want the full range of features and you have a login ID, log in using the links at the top of the page or at https://landing.athabascau.ca/login (logins are secure and encrypted)
Posts made here are the responsibility of their owners and may not reflect the views of Athabasca University.