← Back to DSA Course | Chapter 14: Dynamic Programming | Lesson 4 of 12

0-1 Knapsack समस्या

0-1 knapsack एक bag packing जैसा है जहां हर item या तो लिया जाता है या छोड़ दिया जाता है, weight limit से ऊपर गए बिना सबसे ज़्यादा value देने वाला mix चुनते हुए।

In this page:

  1. Problem Idea
  2. DP State
  3. Transition
  4. Space Optimization
  5. Practice
Syntax
markup 
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for w in range(W + 1):
        dp[i][w] = dp[i - 1][w]                      # skip item
        if weight[i - 1] <= w:
            dp[i][w] = max(dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]])   # take item

Problem Idea

0-1 knapsack problem में, आप एक fixed weight capacity वाले bag में कौन से items pack करें यह चुन रहे हैं total value maximize करने के लिए, लेकिन हर item या तो पूरी तरह लिया जाता है या पूरी तरह छोड़ दिया जाता है — किसी का हिस्सा लेने या इसे दो बार लेने का कोई तरीका नहीं।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	cout << "Choose subset of items, weight <= " << capacity << ", each item fully taken or fully left";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] weights = {2,3,4}, values = {3,4,5};
		int capacity = 5;
		System.out.println("Choose subset of items, weight <= " + capacity + ", each item fully taken or fully left");
	}
}
weights, values, capacity = [2,3,4], [3,4,5], 5
print(f"Choose subset of items, weight <= {capacity}, each item fully taken or fully left")
#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	printf("Choose subset of items, weight <= %d, each item fully taken or fully left", capacity);
	return 0;
}

DP State

dp[i][w] पहले i items सिर्फ उपयोग करते हुए w capacity के knapsack से achievable best total value represent करता है, इसलिए यह table item by item बनाना आखिरकार हर capacity के लिए best possible value दिखाता है जिसकी आपको ज़रूरत हो सकती है।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[4][6] = {0};
	cout << "dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[4][6];
		System.out.println("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot");
	}
}
dp = [[0]*6 for _ in range(4)]
print("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot")
#include <stdio.h>
int main() {
	int dp[4][6] = {0};
	printf("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot");
	return 0;
}

Transition

हर item के लिए आपके पास बिल्कुल दो choices हैं: इसे skip करें और इसके बिना पहले से मिली best value रखें, या इसे लें (अगर यह fit हो) और इसकी value को बची capacity के best result में जोड़ें — DP transition बस इन दो options में से बेहतर लेता है।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5, n = 3;
	int dp[4][6] = {0};
	for (int i = 1; i <= n; i++)
		for (int w = 0; w <= capacity; w++) {
			dp[i][w] = dp[i-1][w];
			if (weights[i-1] <= w) dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
		}
	cout << "Best value with capacity " << capacity << ": " << dp[n][capacity];
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] weights = {2,3,4}, values = {3,4,5};
		int capacity = 5, n = 3;
		int[][] dp = new int[4][6];
		for (int i = 1; i <= n; i++)
			for (int w = 0; w <= capacity; w++) {
				dp[i][w] = dp[i-1][w];
				if (weights[i-1] <= w) dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
			}
		System.out.println("Best value with capacity " + capacity + ": " + dp[n][capacity]);
	}
}
weights, values, capacity, n = [2,3,4], [3,4,5], 5, 3
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
    for w in range(capacity+1):
        dp[i][w] = dp[i-1][w]
        if weights[i-1] <= w:
            dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
print(f"Best value with capacity {capacity}: {dp[n][capacity]}")
#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5, n = 3;
	int dp[4][6] = {0};
	for (int i = 1; i <= n; i++)
		for (int w = 0; w <= capacity; w++) {
			dp[i][w] = dp[i-1][w];
			if (weights[i-1] <= w && dp[i-1][w-weights[i-1]] + values[i-1] > dp[i][w])
				dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1];
		}
	printf("Best value with capacity %d: %d", capacity, dp[n][capacity]);
	return 0;
}

Space Optimization

चूंकि dp[i][w] सिर्फ पिछली row (dp[i-1][...]) पर निर्भर करता है, आप 2D table को एक single 1D array में collapse कर सकते हैं, जब तक आप इसे high capacity से low capacity तक update करें ताकि गलती से कोई item दो बार reuse न हो।

उदाहरण: Space Optimization

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	int dp[6] = {0};
	for (int i = 0; i < 3; i++)
		for (int w = capacity; w >= weights[i]; w--)
			dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
	cout << "1D array updated high-to-low, best value: " << dp[capacity];
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] weights = {2,3,4}, values = {3,4,5};
		int capacity = 5;
		int[] dp = new int[6];
		for (int i = 0; i < 3; i++)
			for (int w = capacity; w >= weights[i]; w--)
				dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
		System.out.println("1D array updated high-to-low, best value: " + dp[capacity]);
	}
}
weights, values, capacity = [2,3,4], [3,4,5], 5
dp = [0]*(capacity+1)
for i in range(3):
    for w in range(capacity, weights[i]-1, -1):
        dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("1D array updated high-to-low, best value:", dp[capacity])
#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	int dp[6] = {0};
	for (int i = 0; i < 3; i++)
		for (int w = capacity; w >= weights[i]; w--)
			if (dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
	printf("1D array updated high-to-low, best value: %d", dp[capacity]);
	return 0;
}

Practice

0-1 knapsack 'choose or don't choose' optimization problems के लिए classic example है, और यही DP shape तब भी reappear होता है जब आप एक hard constraint के तहत items का एक subset select कर रहे हों।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Same DP shape reappears anywhere you select a subset of items under a hard constraint";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Same DP shape reappears anywhere you select a subset of items under a hard constraint");
	}
}
print("Same DP shape reappears anywhere you select a subset of items under a hard constraint")
#include <stdio.h>
int main() {
	printf("Same DP shape reappears anywhere you select a subset of items under a hard constraint");
	return 0;
}
Related Topics

Unbounded Knapsack समस्या · Fractional Knapsack समस्या · DP के साथ Fibonacci · Tabulation और Memoization में अंतर

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. 1D version में capacity को upward loop करना, जो उसी item को कई बार उपयोग होने देता है (वह unbounded knapsack है)।
  2. इसे लेने से पहले यह न जांचना कि item का weight current capacity से ज़्यादा नहीं है।
  3. Table को 0 के अलावा किसी और चीज़ से initialize करना, या dp[i][w] को dp[w][i] के साथ mix up करना।
🔒

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Fibonacci with DP Next Lesson → Unbounded Knapsack

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.