After explaining the knapsack problem yesterday, I was asked what would happen if I could choose any number of elements? This is a variation of the very common knapsack problem, and we just need to make a little change to the original algorithm, so let’s look at it together.
As usual, here’s 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 an infinite number of fruits, multiple of which can be selected.
This time we are also going to sell fruit to get the most out of carrying a limited amount. Fruit: {apple, orange, watermelon} Weight: {1, 2, 3} Yield: {15, 20, 50} Weight: 5.
Let’s also start with a few possible scenarios: 5 Apples (Total weight 5) => 75 Revenue 1 Apple + 2 oranges (Total weight 5) => 55 Revenue 2 apples + 1 watermelon (total weight 5) => 80 Revenue 1 orange + 1 watermelon (total weight 5) => 70 revenue.
We can see that two apples are a perfect match for watermelon, and we get the most out of limited load. The key is we have to give expression to the process through code, let’s analyze, for each of the fruit, we can choose to put in and then to the next round of choice, or do not put in directly to the next round of selection, after each put in A fruit A, we should also choose A put in, know beyond the capacity of backpack, And then in the process we’re going to pick the one of the two options that’s going to bring us the most money.
As always, we implement the algorithm recursively first, and then refine it later. The above description is very clear, so we can write it directly:
private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
if (capacity <= 0 || profits.length == 0|| weights.length ! = profits.length || currentIndex >= profits.length)return 0;
// Continue the loop after the current element is selected. Note that the index is not +1 after the selection
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex]
+ knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);
// Skip the current element and continue the selection
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}
Copy the codeAs you can see, our algorithm is very similar to what we did yesterday, except for some condition changes. Notice that the time here becomes O(2^(N+C)), where N is the number of elements, and C is the maximum load of the backpack, because we can repeatedly select an element.
Now, if you have this problem, if you write a violent recursion, you’re going to be able to instinctively use caching to optimize the algorithm. I don’t need to keep you in suspense, let’s go straight to the code:
private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
int currentIndex) {
if (capacity <= 0 || profits.length == 0|| weights.length ! = profits.length || currentIndex >= profits.length)return 0;
// Check if we have encountered the same subproblem before, if yes, return the result directly
if (dp[currentIndex][capacity] == null) {
// Continue recursion after selection, note that we can continue to select the current element after selection
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
capacity - weights[currentIndex], currentIndex);
// Skip the current element and proceed to the next recursion
int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);
dp[currentIndex][capacity] = Math.max(profit1, profit2);
}
return dp[currentIndex][capacity];
}
Copy the codeAt this time because we sub-problems results are cached in a two-dimensional array, so we are up to the NC times calculation, so our time complexity to O (NC), but now we also can find all discovered usually light cache is not optimal, that we’ll try from another direction, using bottom-up approach to thinking about the problem. (Here comes the exciting part!)
Essentially, we still want to get the most out of each index, each remaining capacitive weight, in the recursion above. We still face two choices,
- If we skip the current element, our maximum benefit at this time must be the same as the maximum benefit of the previous element, i.e
dp[index-1][c]. - Select the current element, then our maximum benefit is the current element plus the maximum benefit of the remaining deadweight, i.e
profit[index] + dp[index][c-weight[index]].
The formula for maximizing profit is dp[index][c] = Max (dp[index-1][c], profit[index] + dp[index][c-weight[index]]). That’s exactly what we were thinking yesterday!
Those of you who have just read yesterday’s article must understand what is going on, and I will not say more, but directly post the code for you to see:
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 deadweight 0 gain
for (int i = 0; i < n; i++)
dp[i][0] = 0;
// Loop through all elements with all weights
for (int i = 0; i < n; i++) {
for (int c = 1; c <= capacity; c++) {
int profit1 = 0, profit2 = 0;
if (weights[i] <= c)
profit1 = profits[i] + dp[i][c - weights[i]];
if (i > 0)
profit2 = dp[i - 1][c]; dp[i][c] = profit1 > profit2 ? profit1 : profit2; }}// The biggest gains are definitely in the bottom right corner
return dp[n - 1][capacity];
}
Copy the codeSee, this problem doesn’t weigh on us at all? With yesterday’s advanced article in hand, we can even optimize this algorithm 200 more times! (Actually twice)
Skin this really happy, the last optimization I will not take you to go, the idea is the same, for you to think, you usually do the algorithm when you must think more, try to convert the topic into the topic we are familiar with, after the successful conversion that we finish ah optimization ah everything with ease.