MHB Versions of the Knapsack problem

  • Thread starter Thread starter mathmari
  • Start date Start date
Click For Summary
The discussion focuses on the two versions of the Knapsack problem: the integer version and the fractional version. In the integer version, items must be taken in whole units, while the fractional version allows for taking parts of items. The integer version is typically solved using dynamic programming, while the fractional version can be addressed with greedy algorithms due to its optimal substructure and greedy choice properties. The optimal substructure property indicates that optimal solutions to subproblems lead to an optimal solution for the overall problem. The conversation seeks clarification on how to identify which version exhibits these properties.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o


I am asked to state the two versions of the Knapsack problem and their differences. Could I formulate it as followed?? (Wondering)

The Knapsack problem is the following:

There are $n$ items, where the $i^{th}$ item has a benefit of $v_i$ and it has weight $w_i$.

We want to pick some items so that we maximize the total benefit while keeping the total weight of $W$.

The difference between the integer and the fractional version of the Knapsack problem is the following:

At the integer version we want to pick each item either fully or we don't pick it.

At the fractional version we can take a part of the item.
 
Physics news on Phys.org
With what type of programming can each of the two versions be solved?

Which of the two versions has the optimal substructure property ?

Which of the two versions has the greedy choice property ?
For the greedy choice property I thought the following:

Wir choose at each step the "best" item, which is the one with the greatest benefit and the smallest weight. We do the same choice until the Knapsack is full or there aren't any objects that fill in the Knapsack.

Is this correct? The optimal substructure property means that each subproblem we have the optimal solution.

Right? But how can we check which of the versions has these properties?
 
First trick I learned this one a long time ago and have used it to entertain and amuse young kids. Ask your friend to write down a three-digit number without showing it to you. Then ask him or her to rearrange the digits to form a new three-digit number. After that, write whichever is the larger number above the other number, and then subtract the smaller from the larger, making sure that you don't see any of the numbers. Then ask the young "victim" to tell you any two of the digits of the...

Similar threads

  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 30 ·
2
Replies
30
Views
5K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 14 ·
Replies
14
Views
4K
Replies
8
Views
5K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 20 ·
Replies
20
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K