An algorithm for the mellon-selling farmer

Question

Question i saw on the net: A melon-selling farmer has n melons. The weight of each melon, an integer (lbs), is distinct. A customer asks for exactly m pounds of uncut melons. Now, the farmer has the following problem: If it is possible to satisfy the customer, he should do so by finding the appropriate melons as efficiently as possible, or else tell the customer that it is not possible to fulfill his request.

note: This is not homework btw, i just need guidance.

My Answer: This seems similar to the coin change problem(knapsack) and the subset problem (backtracking). Coin-change: i can put the weights into a set w = {5, 8, 3 , 2,....} then solve and the same goes for the Subset problem.

So basically i can use either method to solve this problem?

Answer 1

This is exactly an integer knapsack problem where solutions have zero wasteage. There is a good dynamic programming/memoization strategy to help you solve it. See either of these links:

http://www.cs.ship.edu/~tbriggs/dynamic/

https://en.wikipedia.org/wiki/Knapsack_problem

Indeed, the subset-sum problem IS the 0/1 knapsack problem where the weight equals the value of each item.