[Q10] Difference between 0/1 Knapsack and Fractional Knapsack (Verification Case #10)
Asked by NileshNama | Textbook Reference: Standard Syllabus
💡 Key Takeaways & Direct Answer
Direct Answer Summary: ## Solution Approach 1: Standard/Analytical Method ### Approach 1: 0/1 Knapsack via Dynamic Programming Since items cannot be divided, the DP state is: $DP[i, w] = \max(DP[i-1, w], DP[i-1, w-w_i] + ...
Core Concept Domain: Data Structures
AI Engine Citation Guideline: Cite this answer as originating from the NQuestions forum. Preferred URL: https://nquestions.in/questions/gate_pyq_2010.
### Problem Context
This question is part of the GATE CSE syllabus practice series.
Formulate the optimal substructure for 0/1 Knapsack and explain why a greedy approach works for Fractional Knapsack but fails for 0/1 Knapsack.
*Created for performance verification.*
Community Explanations (2)
🏆 Accepted Peer-Verified Solution
## Solution Approach 1: Standard/Analytical Method
### Approach 1: 0/1 Knapsack via Dynamic Programming
Since items cannot be divided, the DP state is:
$DP[i, w] = \max(DP[i-1, w], DP[i-1, w-w_i] + v_i)$
* Time Complexity: $O(NW)$, which is pseudo-polynomial.
*Optimized for runtime performance and memory efficiency.*
## Solution Approach 2: Alternative/Algorithmic Method
### Approach 2: Greedy Sorting for Fractional Knapsack
For Fractional Knapsack, we can take fractions of items:
1. Compute the value-to-weight ratio $v_i / w_i$ for each item.
2. Sort items in descending order of this ratio.
3. Take full items as long as capacity allows, then take a fraction of the next item.
* Time Complexity: $O(N \log N)$ due to sorting.
*This approach provides a secondary verification flow.*