MHB Versions of the Knapsack problem

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread 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?
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
11
Views
2K
Replies
1
Views
1K
Replies
30
Views
5K
Replies
14
Views
4K
Replies
1
Views
2K
Replies
20
Views
3K
Back
Top