अगर आप GATE, Placement, या Competitive Programming की तैयारी कर रहे हैं, तो आपने जरूर सुना होगा कि Algorithm का सबसे tricky और high-scoring topic है – Knapsack Problem. लेकिन ज़्यादातर students इस topic को देखकर डर जाते हैं क्योंकि इसमें Dynamic Programming, Greedy Method, Table Formation जैसे concepts आते हैं।
इस article में आप सीखेंगे:
- Knapsack Problem क्या होता है
- इसके अलग-अलग types – 0/1, Fractional, Unbounded
- कौन-सा approach कब use करना चाहिए
- Step-by-step examples
- Real life applications
- और यह भी कि exam में questions कैसे आते हैं
मतलब यह article पढ़ने के बाद आपका Knapsack Problem डर नहीं रहेगा – बल्कि strength बन जाएगा।
What is Knapsack Problem in Algorithm?
Knapsack Problem एक famous optimization problem है जो हमें सिखाता है कि limited resources के साथ maximum profit कैसे निकाला जाए।
मान लीजिए आपके पास एक bag (knapsack) है जिसकी capacity limited है, और आपके पास कई items हैं – हर item का कुछ weight और कुछ value है।
अब सवाल यह है:
Bag की capacity से ज़्यादा weight नहीं होना चाहिए, लेकिन total value maximum होनी चाहिए।
यही है Knapsack Problem in Algorithm.
Knapsack Problem – Formal Definition
Given:
- n items
- हर item का weight w[i]
- हर item का value v[i]
- Bag की maximum capacity = W
Goal:
ऐसे items चुनना ताकि
Total weight ≤ W और
Total value maximum हो।
यह भी पढ़ें : ग्रीडी एल्गोरिदम क्या है | What is Greedy Algorithm in Hindi
Types of Knapsack Problem
Knapsack Problem मुख्य रूप से चार प्रकार के होते हैं:
1. 0/1 Knapsack Problem
0/1 Knapsack Problem में हर item के लिए केवल दो options होते हैं – या तो item पूरा select किया जाएगा या बिल्कुल नहीं लिया जाएगा, इसलिए इसका नाम 0/1 पड़ा।
इसमें किसी भी item का partial part लेना allowed नहीं होता, जैसे laptop या mobile जिसे आधा नहीं खरीदा जा सकता।
इस problem का goal होता है limited bag capacity के अंदर maximum value हासिल करना, और इसे efficiently solve करने के लिए आमतौर पर Dynamic Programming approach का use किया जाता है।
Example:
आप laptop खरीद रहे हो – या तो laptop खरीदोगे या नहीं, आधा laptop नहीं खरीद सकते।
2. Fractional Knapsack Problem
Fractional Knapsack Problem में items को fraction में लेने की permission होती है, मतलब अगर पूरा item नहीं ले सकते तो उसका कुछ हिस्सा लिया जा सकता है, जैसे rice या oil।
इस problem में हम items को उनके value/weight ratio के according sort करते हैं और फिर greedily highest ratio वाले items पहले चुनते हैं।
इस variation को solve करने के लिए Greedy Algorithm सबसे best approach माना जाता है।
Example:
आप rice खरीद रहे हो – 1 kg या 0.5 kg, जैसा चाहो ले सकते हो।
3. Bounded Knapsack
Bounded Knapsack Problem में हर item की quantity limited होती है, यानी हर item को एक fixed number of times ही लिया जा सकता है। यह 0/1 और Unbounded Knapsack के बीच का case होता है, जहाँ कुछ items limited होते हैं लेकिन zero या infinite नहीं।
इस तरह की problems आमतौर पर warehouse या inventory management में देखने को मिलती हैं और इन्हें solve करने के लिए Dynamic Programming techniques का use किया जाता है।
4. Unbounded Knapsack
Unbounded Knapsack Problem में हर item की unlimited supply available होती है, यानी आप एक ही item को बार-बार चुन सकते हैं जब तक bag की capacity allow करे।
इसका example coins या chocolates जैसा होता है, जहाँ एक ही type की चीज कई बार ली जा सकती है।
इस problem को भी आमतौर पर Dynamic Programming के through solve किया जाता है और यह resource allocation जैसे scenarios में काफी useful होता है।
यह भी पढ़ें : Dynamic Programming Notes for GATE 2026 CS & IT – Complete Guide
Algorithm Approaches to Solve Knapsack Problem
Knapsack Problem को solve करने के लिए अलग-अलग algorithm approaches use की जाती हैं क्योंकि हर variation की nature अलग होती है। कहीं items को fraction में लिया जा सकता है, कहीं नहीं, और कहीं unlimited quantity available होती है।
इसलिए हमें problem के type के according सही method choose करना पड़ता है। नीचे main approaches को tutorial style में समझाया गया है।
1. Greedy Method (Used For Fractional Knapsack Problem)
Greedy algorithm का basic idea होता है कि हर step पर हम सबसे best option choose करें। Fractional Knapsack में हम हर item का value/weight ratio निकालते हैं और फिर सभी items को इस ratio के descending order में sort करते हैं।
इसके बाद bag की capacity भरने तक highest ratio वाले items पहले pick करते हैं। अगर पूरा item fit नहीं होता, तो उसका fractional part ले लेते हैं।
इस approach की time complexity O(n log n) होती है क्योंकि sorting करनी पड़ती है, और यह method हमेशा optimal solution देता है – लेकिन सिर्फ Fractional Knapsack के लिए।
2. Dynamic Programming Approach (Used For 0/1 Knapsack)
जब items को fraction में नहीं लिया जा सकता या quantities limited / unlimited हों, तब Greedy fail हो जाता है। ऐसे cases में हम Dynamic Programming (DP) use करते हैं।
DP में हम एक table बनाते हैं जहाँ dp[i][w] represent करता है कि first i items और capacity w के साथ maximum value कितनी हो सकती है। हम हर item के लिए दो choices consider करते हैं – उसे लेना या छोड़ना। फिर previous results को reuse करके final answer तक पहुँचते हैं।
इस approach की time complexity O(nW) होती है और यह 0/1, Bounded और Unbounded Knapsack सभी में correct result देता है।
3. Backtracking / Recursive Approach – Concept Understanding के लिए
Backtracking में हम सभी possible combinations generate करते हैं और हर combination के लिए check करते हैं कि weight limit के अंदर maximum value कितनी मिल रही है।
यह method concept समझने के लिए useful है, लेकिन large input पर बहुत slow हो जाता है क्योंकि इसकी complexity exponential होती है।
4. Branch and Bound – Optimized Searching Technique
यह method backtracking का optimized version है जिसमें unnecessary branches को prune कर दिया जाता है, ताकि computation कम हो।
इसमें upper bound calculate करके unpromising solutions को skip कर दिया जाता है।
यह technique large scale optimization problems में useful होती है, लेकिन implementation थोड़ा complex होता है।
Applications of the Knapsack Problem
- Investment Planning: Limited budget में best stocks या assets select करना ताकि maximum profit मिले।
- Logistics & Transportation: Truck या container की limited capacity में सबसे ज्यादा valuable goods load करना।
- Memory Management: Computer की limited RAM या cache में सबसे important programs और data रखना।
- E-commerce Recommendation Systems: Limited product slots में सबसे ज्यादा profitable products show करना।
- Manufacturing Industry: Limited raw material से maximum profit वाले products produce करना।
- Project Management: Limited time और resources में सबसे valuable tasks choose करना।
- Network Bandwidth Allocation: Limited bandwidth में priority वाले data packets transmit करना।
- Travel Packing: Limited luggage capacity में सबसे useful items pack करना।
- Scientific Research: Limited funding में maximum impact वाले experiments select करना।
- Game Development: In-game limited resources को use करके maximum rewards achieve करना।
Why Knapsack Problem is Important?
- GATE exam में हर साल पूछा जाता है
- Placement interviews में favorite topic
- Competitive Programming में core concept
- Real-world problems – budget planning, resource allocation
अगर आपने Knapsack Problem अच्छे से समझ लिया, तो आप Dynamic Programming master बनने के रास्ते पर हो।
Real Life Applications of Knapsack Problem
| Field | Use |
| Investment | Limited money में best stocks choose करना |
| Logistics | Truck में limited space में maximum goods |
| Computer Memory | RAM allocation |
| Project Management | Limited time में best tasks choose करना |
यह भी पढ़ें : Data Structure in Hindi – Stack, Queue, Tree कैसे काम करते हैं (Guide 2025)
निष्कर्ष (Conclusion)
इस पूरे article में आपने detail में समझा कि Knapsack Problem in Algorithm क्या होता है, इसके main variations कौन-कौन से हैं और उन्हें solve करने के लिए कौन-से algorithm approaches सही रहते हैं।
आपने देखा कि Fractional Knapsack में Greedy method best काम करता है, जबकि 0/1, Bounded और Unbounded Knapsack के लिए Dynamic Programming सबसे reliable solution देती है।
साथ ही real-life applications और examples से यह clear हो गया कि यह सिर्फ exam का topic नहीं, बल्कि practical world में भी बहुत important concept है।
अगर आप GATE, placement या competitive programming की तैयारी कर रहे हैं, तो Knapsack Problem को अच्छे से समझना आपकी algorithm skills को एक strong level तक ले जाएगा।
FAQs
Q1. क्या Greedy 0/1 Knapsack solve कर सकता है?
Ans. नहीं, Greedy सिर्फ Fractional Knapsack में सही काम करता है।
Q2. 0/1 Knapsack को क्यों DP से solve करते हैं?
Ans. क्योंकि इसमें overlapping sub-problems होते हैं।
Q3. Knapsack NP-Complete क्यों है?
Ans. क्योंकि इसका optimal solution polynomial time में नहीं मिलता।
यह भी पढ़ें :
