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?
 
There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...

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