Unbounded Knapsack समस्या

Unbounded knapsack endless supplies वाले एक store से एक bag pack करने जैसा है, इसलिए आप उसी item को जितनी बार चाहें उतनी बार pick कर सकते हैं।

In this page:

Problem Idea
Difference from 0-1
DP Transition
Coin-Like Problems
Practice

Syntax

markup

dp = [0] * (W + 1)
for w in range(W + 1):
    for i in range(n):
        if weight[i] <= w:
            dp[w] = max(dp[w], value[i] + dp[w - weight[i]])

Problem Idea

Unbounded knapsack 0-1 version से एक rule बदलता है: हर item type की कोई supply limit नहीं, इसलिए आप उसी item को जितनी बार यह fit हो उतनी बार लेने के लिए free हैं — किसी भी denomination के stamps जितनी बार चाहें खरीदने जैसा।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations");
	}
}

print("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations")

#include <stdio.h>
int main() {
	printf("Unbounded knapsack: same item can be taken multiple times, like unlimited stamp denominations");
	return 0;
}

Difference from 0-1

State और objective 0-1 knapsack जैसे ही दिखते हैं, लेकिन चूंकि एक item reuse किया जा सकता है, item i consider करना इसे भविष्य के consideration से उस तरह नहीं हटाता जैसे 0-1 knapsack में होता है।

उदाहरण: Difference from 0-1

#include <iostream>
using namespace std;
int main() {
	cout << "Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration");
	}
}

print("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration")

#include <stdio.h>
int main() {
	printf("Same state and goal as 0-1 knapsack, but taking item i doesn't remove it from future consideration");
	return 0;
}

DP Transition

एक item लेने के बाद, transition अब भी बची capacity के लिए उसी item को फिर से consider कर सकता है, बजाय strictly अगले item पर move करने के — यही वह एक line of code है जो unbounded को 0-1 knapsack से अलग करती है।

उदाहरण: DP Transition

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 6;
	int dp[7] = {0};
	for (int w = 1; w <= capacity; w++)
		for (int i = 0; i < 3; i++)
			if (weights[i] <= w) dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
	cout << "Same item reconsidered for leftover capacity, 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 = 6;
		int[] dp = new int[7];
		for (int w = 1; w <= capacity; w++)
			for (int i = 0; i < 3; i++)
				if (weights[i] <= w) dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
		System.out.println("Same item reconsidered for leftover capacity, best value: " + dp[capacity]);
	}
}

weights, values, capacity = [2,3,4], [3,4,5], 6
dp = [0]*(capacity+1)
for w in range(1, capacity+1):
    for i in range(3):
        if weights[i] <= w:
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("Same item reconsidered for leftover capacity, best value:", dp[capacity])

#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 6;
	int dp[7] = {0};
	for (int w = 1; w <= capacity; w++)
		for (int i = 0; i < 3; i++)
			if (weights[i] <= w && dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
	printf("Same item reconsidered for leftover capacity, best value: %d", dp[capacity]);
	return 0;
}

Coin-Like Problems

यह 'reuse allowed' shape बिल्कुल वही structure है जो coin-change (एक target amount तक पहुंचने के लिए unlimited coins उपयोग करना) और rod-cutting (total value maximize करने के लिए एक rod को pieces में काटना) के पीछे है, यही कारण है कि वे आमतौर पर इस topic के ठीक बाद सिखाए जाते हैं।

उदाहरण: Coin-Like Problems

#include <iostream>
using namespace std;
int main() {
	cout << "Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape");
	}
}

print("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape")

#include <stdio.h>
int main() {
	printf("Coin change (reach a target amount) and rod-cutting share this exact 'reuse allowed' DP shape");
	return 0;
}

Practice

जब भी एक problem statement एक item, denomination, या piece को बिना limit के reuse होने देती है, वह 0-1 version के बजाय unbounded knapsack DP pattern तक पहुंचने का signal है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP");
	}
}

print("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP")

#include <stdio.h>
int main() {
	printf("Item/denomination/piece reusable without limit? That's the signal for unbounded knapsack DP");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson 0-1 Knapsack Next Lesson → Longest Common Subsequence