Log In

Knapsack problem

Posted on: September 24th, 2013 by
Comments Disabled

Suppose you have goods numbered 1,2,3....n that you want to transport. Good i has value V_i and weight W_i. You want to transport as much value as possible over an airplane. However, you are allowed to transfer a maximum weight of W. You wish to maximize the total value of goods transported subject to the constraint that the total weight is at most W. Assume that the weights W_1,W_2,....W_n are all integers. Give an algorithm that takes O(nW) time to find the best subset of items to carry in the airplane.

via Wikipedia (SPOILER warning)


Comments are closed.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}