worldofitech
The Knapsack Problem is a famous Dynamic Programming Problem that falls in the optimization category.
It derives it’s name from a situation where, given a set of items with explicit loads and assigned values, the objective is to maximize the value in a knapsack while remaining inside the weight constraint.
In this tutorial, you will learn:
Contents
What is the Knapsack Problem?
Knapsack Problem algorithm is a useful issue in combinatorics. In the general store there are n packages (n ≤ 100) the package I has weight W[i] ≤ 100 and worth V[i] ≤ 100. A thief breaks into the supermarket, the thief can’t convey weight exceeding (M ≤ 100). The issue to be settled here is: which packages the thief will remove to get the highest value?
Input:
• Maximum weight M and the quantity of packages n.
• Array of weight W[i] and relating value V[i].
Output:
• Maximize value and relating weight in capacity.
• Which packages the thief will remove.
Knapsack algorithm can be additionally divided into two types:
• The 0/1 Knapsack issue using dynamic programming. In this Knapsack algorithm type, each package can be taken or not taken. Additionally, the thief can’t take a partial measure of a taken package or take a package more than once. This sort can be settled by Dynamic Programming Approach.
• Fractional Knapsack issue algorithm. This sort can be tackled by Greedy Strategy.
Brief Introduction of Dynamic Programming
In the divide-and-conquer system, you divide the issue to be addressed into subproblems. The subproblems are additionally divided into smaller subproblems. That task will proceed until you get subproblems that can be addressed without any problem. Notwithstanding, during the time spent such division, you may experience a similar issue ordinarily.
The fundamental thought of Knapsack dynamic programming is to use a table to store the solutions of tackled subproblems. On the off chance that you face a subproblem once more, you simply need to take the solution in the table without tackling it once more. Accordingly, the algorithms designed by dynamic programming are very effective.
To tackle an issue by dynamic programming, you need to do the accompanying tasks:
• Find solutions of the smallest subproblems.
• Find out the formula (or rule) to assemble an answer of subproblem through solutions of even smallest subproblems.
• Create a table that stores the solutions of subproblems. Then, at that point calculate the solution of subproblem as indicated by the discovered formula and save to the table.
• From the solved subproblems, you discover the solution of the first issue.
Analyze the 0/1 Knapsack Problem
While analyzing down 0/1 Knapsack issue using Dynamic programming, you can track down some observable focuses. The value of the knapsack algorithm relies upon two variables:
- How numerous packages are being thought of
- The leftover weight which the knapsack can store.
Along these lines, you have two variable amounts.
With dynamic programming, you have useful data:
- the target capacity will rely upon two variable amounts
- the table of choices will be a 2-dimensional table.
In the event that calling B[i][j] is the maximum conceivable value by choosing in packages {1, 2, …, i} with weight limit j.
• The maximum value when chosen in n packages with the weight limit M is B[n][M]. In other words: When there are I packages to pick, B[i][j] is the optimal weight when the maximum weight of the knapsack is j.
• The optimal weight is in every case not exactly or equivalent to the maximum weight: B[i][j] ≤ j.
For instance: B[4][10] = 8. It means that in the optimal case, the total weight of the chose packages is 8, when there are 4 first packages to choose from (first to fourth package) and the maximum weight of the knapsack is 10. It’s not necessary that each of the 4 items are chosen.
Formula to Calculate B[i][j]
Input, you define:
• W[i], V[i] are thusly the weight and value of package I, in which I {1, … , n}.
• M is the maximum weight that the knapsack can convey.
In the case of just having just 1 package to pick. You calculate B[1][j] for each j: which means the maximum weight of the knapsack ≥ the weight of the first package
B[1][j] = W[1]
With as weight limit j, the optimal determinations among packages {1, 2, …, I – 1, i} to have the largest value will have two prospects:
In the event that package I isn’t chosen, B[i][j] is the maximum possible value by choosing among packages {1, 2, …, I – 1} with weight limit of j. You have:
B[i][j] = B[i – 1][j]
On the off chance that package I is chosen (obviously possibly think about this situation when W[i] ≤ j) then, at that point B[i][j] is equivalent to the value V[i] of package I in addition to the maximum value can be obtained by choosing among packages {1, 2, …, I – 1} with weight limit (j – W[i]). That is, in terms of the value you have:
B[i][j] = V[i] + B[i – 1][j – W[i]]
Because of the production of B[i][j], which is the maximum possible value, B[i][j] will be the maximum of the over 2 values.
Premise of Dynamic Programming
Along these lines, you need to consider in the event that it is better to pick package i or not. From that point you have the formula as follows:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
It is not difficult to see B[0][j] = maximum value possible by choosing from 0 packages = 0.
Calculate the Table of Options
You build a table of choices dependent on the above recursive formula. To check if the outcomes are right (if not exactly, you rebuild the target work B[i][j]). Through the production of the target work B[i][j] and the table of alternatives, you will orient the tracking.
Table of alternatives B incorporates n + 1 lines, M + 1 columns,
- Firstly, filled with the basis of dynamic programming: Line 0 incorporates all zeros.
- Using recursive formula, use line 0 to calculate line 1, use line 1 to calculate line 2, and so on … until all lines are calculated.
Trace
While calculating the table of alternatives, you are interested in B[n][M] which is the maximum value obtained while choosing in all n packages with the weight limit M.
- On the off chance that B[n][M] = B[n – 1][M], package n isn’t chosen, you trace B[n – 1][M].
- On the off chance that B[n][M] ≠ B[n – 1][M], you notice that the optimal determination has the package n and trace B[n – 1][M – W[n]].
Continue to trace until reaching row 0 of the table of options.
Algorithm to Look Up the Table of Options to Find the Selected Packages
Note: If B[i][j] = B[i – 1][j], the package I isn’t chosen. B[n][W] is the optimal total value of package put into the knapsack.
Steps for tracing:
- Stage 1: Starting from I = n, j = M.
- Stage 2: Look in column j, up from base, you discover the line I such that B[i][j] > B[i – 1][j]. Mark chosen package I: Select [i] = true;
- Stage 3: j = B[i][j] – W[i]. On the off chance that j > 0, go to stage 2, in any case go to stage 4
- Stage 4: Based on the table of choices to print the selected packages.
Java Code
public void knapsackDyProg(int W[], int V[], int M, int n) {
int B[][] = new int[n + 1][M + 1];
for (int i=0; i<=n; i++)
for (int j=0; j<=M; j++) {
B[i][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= M; j++) {
B[i][j] = B[i - 1][j];
if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
}
System.out.print(B[i][j] + " ");
}
System.out.print("\n");
}
System.out.println("Max Value:\t" + B[n][M]);
System.out.println("Selected Packs: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
Explanation of Knapsack code:
- Create table B[][]. Set default value for each cell is 0.
- Build table B[][] in bottom-up manner. Calculate the table of alternatives with the retrieval formula.
- Calculate B[i][j]. In the event that you don’t choose package I.
- Then, at that point assess: assuming you select package I, it will be more valuable reset B[i][j].
- Trace the table from now n to row 0.
- On the off chance that you pick package n. When select package n, can just add weight M – W[n – 1].
In this tutorial, you have two examples. Here is java code to run the above program with two examples:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackDyProg(W, V, M, n);
}
You have the output:
First Example:
0 0 0 3 3 3 3 3 3 3 3 3 0 0 0 3 4 4 4 7 7 7 7 7 0 0 0 3 4 4 4 7 7 8 8 8 0 0 0 3 4 4 4 7 7 10 10 10 0 0 0 3 4 4 4 7 8 10 10 11 Max Value: 11 Selected Packs: Package 5 with W = 4 and Value = 4 Package 2 with W = 4 and Value = 4 Package 1 with W = 3 and Value = 3
Second Example:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15 Max Value: 15 Selected Packs: Package 5 with W = 4 and Value = 10 Package 4 with W = 1 and Value = 2 Package 3 with W = 1 and Value = 1 Package 2 with W = 2 and Value = 2
Related:
What is Waterfall Model in SDLC? Advantages and Disadvantages
Incremental Model in SDLC: Use, Advantage & Disadvantage
Spiral Model: When to Use? Advantages & Disadvantages
What is RAD Model? Phases, Advantages and Disadvantages
Prototyping Model in Software Engineering: Methodology, Process, Approach
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your projects with us.
