Hello, everyone. Recently, due to a lot of things I have to do at the beginning of my job, I failed to update it for a period of time. From today on, I will slowly restore the update and share my experience in algorithm with you.
Haven’t said dynamic programming for a long time, after the last analysis, we should have a general understanding of dynamic programming, today we look at a classic problem –0/1 backpack problem. Maybe some of you think the knapsack problem is very simple, just write a judgment condition, recursive implementation can solve it. But we still have a lot to think about in order to get the optimal solution.
Let’s take a look at the definition: Given the weight and yield of N fruits, we need to put them into a backpack with a capacity of C, so that the fruit in the bag has the highest yield with a total weight of NO more than C, assuming that there is a limited number of fruits and only one of each kind can be chosen.
It’s a short question, it’s easy to understand, but let’s make it a little bit more specific. Let’s do an example. Fruit: {apples, oranges, bananas, watermelons} Weight: {2, 3, 1, 4} Yield: {4, 5, 3, 7} Backpack weight: 5
Try different combinations: Apples + oranges (total weight 5) => 9 Apples + bananas (total weight 3) => 7 oranges + bananas (total weight 4) => 8 bananas + watermelon (total weight 5) => 10
We can see that watermelon and banana are the perfect match, giving us the maximum benefit under the limited weight limit. Let’s try to describe it algorithmically. As I said before, the simplest is violent recursion, where each time we encounter a fruit, we have two choices, either to put it in while the backpack still has room for it, or not to put it in at all, which will help us list all the scenarios, and we’ll only take the one with the most benefit.
private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
if (capacity <= 0 || currentIndex >= profits.length)
return 0;
// Process the remaining elements recursively in case the current element can be put into the backpack
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity - weights[currentIndex], currentIndex + 1);
// Skip the current element and process the remaining elements
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}
Copy the codeThe time complexity of such a solution is in O(2^n), and a slightly larger amount of data will be significantly time-consuming.
private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
int currentIndex) {
if (capacity <= 0 || currentIndex >= profits.length)
return 0;
// If the result is already calculated, return it directly
if(dp[currentIndex][capacity] ! =null)
return dp[currentIndex][capacity];
// Process the remaining elements recursively in case the current element can be put into the backpack
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
capacity - weights[currentIndex], currentIndex + 1);
// Skip the current element and process the remaining elements
int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);
dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}
Copy the codeWell, ultimately all the results are stored in this two-dimensional array, and we can be sure that we can’t have more than NC subproblems, where N is the number of elements and C is the weight of the backpack, which means that at this point we only have O(NC) in time and space.
That’s not the end of the story, but let’s try to think about this problem from the bottom up, and see if we can get a better solution. Essentially, we want to get the most out of each index, each remaining capacitive weight, in the recursion above. With element 3, we want to get as much money as we can. With element 4, we still want to get the most out of it. (After all, maximizing profit is everyone’s goal.)dp[I][c] represents the maximum return from the initial I =0 to the current I. That leaves us with only two options at a time:
- Skip the current element, so we’re only going to get the most out of this process
dp[i-1][c]. - As long as the weight can fit, the maximum benefit of putting this element in is zero
profit[i] + dp[i-1][c-weight[i]].
Ultimately, the maximum we want to get is the maximum of these two. Dp [I] [c] = Max (dp [c], [I – 1] profit [I] + dp [I – 1) [c – weight [I]]).
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
if (capacity <= 0 || profits.length == 0|| weights.length ! = profits.length)return 0;
int n = profits.length;
int[][] dp = new int[n][capacity + 1];
// 0 space returns 0
for(int i=0; i < n; i++)
dp[i][0] = 0;
// When dealing with the first element, as long as its weight can be carried by the back, it is definitely more profitable to put it in than not
for(int c=0; c <= capacity; c++) {
if(weights[0] <= c)
dp[0][c] = profits[0];
}
// Loop through all elements with all weights
for(int i=1; i < n; i++) {
for(int c=1; c <= capacity; c++) {
int profit1= 0, profit2 = 0;
// Contains the current element
if(weights[i] <= c)
profit1 = profits[i] + dp[i-1][c-weights[i]];
// Contains no current element
profit2 = dp[i-1][c];
// take the maximum valuedp[i][c] = Math.max(profit1, profit2); }}// The last element of dp is the maximum value
return dp[n-1][capacity];
}
Copy the codeSo the time and space complexity is order N times C.
So how do you find the chosen element? Actually very simple, we said before, not to select the current element, the current maximum gain before processing an element when the biggest profits, in other words, as long as the two elements are the same, the up and down in the dp, index represents element is not selected, the first in the dp where different total return is the location of the selected elements.
private void printSelectedElements(int dp[][], int[] weights, int[] profits, int capacity) {
System.out.print("Selected weights:");
int totalProfit = dp[weights.length - 1][capacity];
for (int i = weights.length - 1; i > 0; i--) {
if(totalProfit ! = dp[i -1][capacity]) {
System.out.print(""+ weights[i]); capacity -= weights[i]; totalProfit -= profits[i]; }}if(totalProfit ! =0)
System.out.print("" + weights[0]);
System.out.println("");
}
Copy the codeIs this algorithm simple enough? But I don’t think we can stop there, because we went to a lot of trouble to do it in a different way, to get the same complexity and we’re done? Let’s look at our algorithm again. We found that when we deal with the current element, all we need is the maximum return of each index in the previous element, and we don’t care about the data before that, so this is an optimization point, we can greatly reduce the size of DP.
static int solveKnapsack(int[] profits, int[] weights, int capacity) {
if (capacity <= 0 || profits.length == 0|| weights.length ! = profits.length)return 0;
int n = profits.length;
// We only need the result of the previous time to get the optimal solution, so we can reduce the array to two lines
// We use 'I %2' for 'I' and '(I -1)%2' for 'I -1'
int[][] dp = new int[2][capacity+1];
// When dealing with the first element, as long as its weight can be carried by the back, it is definitely more profitable to put it in than not
for(int c=0; c <= capacity; c++) {
if(weights[0] <= c)
dp[0][c] = dp[1][c] = profits[0];
}
// Loop through all elements with all weights
for(int i=1; i < n; i++) {
for(int c=0; c <= capacity; c++) {
int profit1= 0, profit2 = 0;
// Contains the current element
if(weights[i] <= c)
profit1 = profits[i] + dp[(i-1) %2][c-weights[i]];
// Contains no current element
profit2 = dp[(i-1) %2][c];
// take the maximum value
dp[i%2][c] = Math.max(profit1, profit2); }}return dp[(n-1) %2][capacity];
}
Copy the codeAnd then we’re left with order N, which, hey, hey, is a pretty good result. Dp [c] and dp[c-weight[I] are the only values we need. Can we put all the results in a one-dimensional array?
- When we access dp[I], it has not been overwritten by the results of the current iteration.
- When we visit
dp[c-weight[i]]If weight[I]>0, thendp[c-weight[i]]It could have been covered up.
This is not a problem, as long as we change the processing order :c :capacity–>0. If we go backwards, we’re going to be able to make sure that we don’t use this value any time we need to change the DP, if you think about it. The idea is clear, that handwritten code is very simple:
static int solveKnapsack(int[] profits, int[] weights, int capacity) {
if (capacity == 0 || profits.length == 0|| weights.length ! = profits.length) {return 0;
}
int n = profits.length;
int[] dp = new int[capacity + 1];
for (int i = 1; i <= capacity; i++) {
if (weights[0] <= i) {
dp[i] = profits[0]; }}for (int j = 1; j < n; j++) {
for (int c = capacity; c >= 0; c--) {
int profit1 = 0;
if (weights[j] <= c) {
profit1 = profits[j] + dp[c - weights[j]];
}
intprofit2 = dp[c]; dp[c] = Math.max(profit1, profit2); }}return dp[capacity];
}
Copy the codeNow our algorithm is optimal! To summarize, dynamic programming is a way to reduce unnecessary memory consumption and reuse the results of previous problems to solve the current problem in the least amount of time. The idea is so simple, but about memory optimization, it has to rely on the accumulation of experience, we practice doing hand is familiar.