Blog
5 BEST Sauce Labs Competitors & Alternatives (2021)
Sauce Labs is an application that allows you to test your mobile applications and website across...
Knapsack Problem algorithm is a very helpful problem in combinatorics. In the supermarket there are n packages (n ≤ 100) the package i has weight W[i] ≤ 100 and value V[i] ≤ 100. A thief breaks into the supermarket, the thief cannot carry weight exceeding M (M ≤ 100). The problem to be solved here is: which packages the thief will take away to get the highest value?
Input:
Output:
Knapsack algorithm can be further divided into two types:
In this tutorial, you will learn:
In the divide-and-conquer strategy, you divide the problem to be solved into subproblems. The subproblems are further divided into smaller subproblems. That task will continue until you get subproblems that can be solved easily. However, in the process of such division, you may encounter the same problem many times.
The basic idea of Knapsack dynamic programming is to use a table to store the solutions of solved subproblems. If you face a subproblem again, you just need to take the solution in the table without having to solve it again. Therefore, the algorithms designed by dynamic programming are very effective.
To solve a problem by dynamic programming, you need to do the following tasks:
When analyzing 0/1 Knapsack problem using Dynamic programming, you can find some noticeable points. The value of the knapsack algorithm depends on two factors:
Therefore, you have two variable quantities.
With dynamic programming, you have useful information:
If calling B[i][j] is the maximum possible value by selecting in packages {1, 2, ..., i} with weight limit j.
For example: B[4][10] = 8. It means that in the optimal case, the total weight of the selected packages is 8, when there are 4 first packages to choose from (1st to 4th package) and the maximum weight of the knapsack is 10. It is not necessary that all 4 items are selected.
Input, you define:
In the case of simply having only 1 package to choose. You calculate B[1][j] for every j: which means the maximum weight of the knapsack ≥ the weight of the 1st package
B[1][j] = W[1]
With the weight limit j, the optimal selections among packages {1, 2, ..., i – 1, i} to have the largest value will have two possibilities:
B[i][j] = B[i – 1][j]
B[i][j] = V[i] + B[i – 1][j – W[i]]
Due to the creation of B[i][j], which is the maximum possible value, B[i][j] will be the max of the above 2 values.
So, you have to consider if it is better to choose package i or not. From there you have the recursive formula as follows:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
It is easy to see B[0][j] = maximum value possible by selecting from 0 package = 0.
You build a table of options based on the above recursive formula. To check if the results are correct (if not exactly, you rebuild the objective function B[i][j]). Through the creation of the objective function B[i][j] and the table of options, you will orient the tracing.
Table of options B includes n + 1 lines, M + 1 columns,
When calculating the table of options, you are interested in B[n][M] which is the maximum value obtained when selecting in all n packages with the weight limit M.
Continue to trace until reaching row 0 of the table of options.
Note: If B[i][j] = B[i – 1][j], the package i is not selected. B[n][W] is the optimal total value of package put into the knapsack.
Steps for tracing:
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:
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:
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
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
Sauce Labs is an application that allows you to test your mobile applications and website across...
Freelance websites are places where you can earn money for yourself, rather than for a particular...
Download PDF 1) What Is SDLC? SDLC is an abbreviation of Software Development Life Cycle. SDLC is...
While working on a Linux operating system, you may need to communicate with other devices . For...
Today's market is flooded with an array of Big Data tools and technologies. They bring cost...
Here are Kubernetes Interview Questions for fresher as well as experienced candidates to get the...