CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
user14512063
user14512063

Reputation:

Solving fractional knapsack problem with dynamic programming

A few days ago, I was reading about greedy algorithms and dynamic programming for the fractional knapsack problem, and I saw that this problem can be solved optimally with the greedy method. Can anyone give an example or a solution to solve this problem with the dynamic programming method?

P.S: I know that the greedy method is the best way to solve this question, but I want to know how dynamic programming works for this issue.

Upvotes: 1

Views: 4299

Answers (1)

Ekesh Kumar
Ekesh Kumar

Reputation: 525

Yes, you can solve the problem with dynamic programming.

Let f(i, j) denote the maximum total value that can be obtained using the first i elements using a knapsack whose capacity is j.

If you are familiar with the 0-1 knapsack problem, then you may remember that we had the exact same function. However, the recurrence for the 0-1 knapsack problem was f(i, j) = max{f(i - 1, j), V[i] + f(i - 1, j - W[i])} (the first argument considers the case in which we don't take the item at index i, and the second argument considers the case in which we do take the item at index i).

In the fractional knapsack problem, we are allowed to take fractional amounts of some item. Thus, our recurrence would look something like, f(i, j) = max{f(i - 1, j), delta * V[i] f(i - 1, j - delta * W[i]) over all possible values of delta, where delta represents the amount of the item that we are taking.

Now if you increment delta in sufficiently small increments, you should get the correct answer.

Upvotes: 1

Related Questions