0/1 Knapsack Problem Dynamic Programming
Why Stack Overflow recommends it
Stack Overflow users link it when answering knapsack questions, since the table-building walkthrough explains the bottom-up approach and which items get chosen more clearly than written answers.
Recommended by 4 people across 4 different months, 2016 to 2024.
What it is
A 15-minute walkthrough of the 0/1 knapsack problem solved with dynamic programming, where a bag with a weight limit must be filled with items to maximize total value. Tushar Roy builds the DP table step by step and links to Java code on GitHub.
What people said
Recommends Orhan Tuncer · 2016-02 · Stack Overflow · on “Smallest sum of subarray with sum greater than a given value”
As the other answers indicate this is a NP-Complete problem which is called the " Knapsack Problem [LINK] ". So there is no polynomial solution. But it has a pseudo polynomial time algorithm. This explains what pseudo polynomial is [LINK] . A visual explanation of the algorithm [this video] . And some code [LINK] . If this is work related (I met this problem a few times already, in various disguises) I suggest introducing additional restrictions to simplify it. If it was a general question you may want to check other NP-Complete problems as well. One such list. [LINK] Edit 1: AliVar made a good point. The given problem searches for Y > X and the knapsack problem searches for Y < X. So the answer
Recommends Orhan Tuncer · 2016-02 · Stack Overflow · on “Knapsack Algorithm: Why we use wt[i-1] instead of wt[i]”
That gives us the best value we can get if we do not select item i. Consider items (value,volume); (2,1), (3,2), (4,5) and a bag of volume 5. When we are dealing with the third item we can have a value of 4. But if we do not take it, we can have our previous max value which is 5. Check this video. [this video]
Recommends displayName · 2017-03 · Stack Overflow · on “Fill a block of the maximum of data”
This is indeed a 0/1 knapsack problem. I am able to solve it. See this youtube video [this video] and you will be able to as well.
Recommends monster · 2017-09 · Stack Overflow · on “How to get the list of selected items in 0-1 knapsack?”
Check this link - [this video] It has a video tutorial on how to do it and i think it will be easier to understand than written solution
Recommends Praveen Ojha · 2018-12 · Stack Overflow · on “Knapsack algorithm, weird behavior (python3)”
Suppose q=-2 (a negative value) Therefore you are filling your base cases with -2 . That is -2 is returned for base cases of your function which is then getting added to the answer on each step in recursion. Try a bottom up approach with a 2D array. You can look at that here [this video] . In your case you are filling matrix base cases with -2. def knapSack(W, wt, val, n): K = [[0 for x in range(W+1)] for x in range(n+1)] q=-2 #Make it zero for correct answer # Build table K[][] in bottom up manner for i in range(n+1): for w in range(W+1): if i==0 or w==0: K[i][w] = q #Here you are assigning negative value elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) else: K[i][w] = K
Cites Zevgon · 2024-10 · Stack Overflow · on “Maximize distance while pushing crates”
I'm struggling to write an algorithm for this problem. What approach can be used to solve it? Problem There's a company called CratePushers, whose employees are willing to push crates for money. Their employees have certain attributes: Each employee pushes crates at a certain rate. For example, Alice might push crates at 3 feet per dollar, and Bob might push them at 2 feet per dollar Each employee has a certain set of crate types that they're capable of pushing. For example, Alice might only be able to push crates that are labeled with an A, B, or C, while Bob might only be able to push crates that are labeled with an A or a D Each employee might have a limit to the total number of crates th