Special multidimensional cost backpack problem solution

This is the 9th day of my participation in Gwen Challenge

Topic describes

This is the 879. Profit plan on LeetCode. Difficulty is difficult.

Tag: “Dynamic programming”, “Exclusion Principle”, “Mathematics”, “Knapsack problem”, “Multidimensional Knapsack”

There are n employees in the group, and they can perform all kinds of work to create profits.

Type I, which produces profit[I], requires the participation of group[I] members. If members are involved in one, they cannot be involved in the other.

Any work that generates at least a subset of minProfit is called a profit plan. And the maximum number of working members is N.

How many plans are there to choose from? Because the answer is large, return the value of 109+7, 10^9 +7, 109+7.

Example 1:

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2 In general, there are two kinds of plans.Copy the code

Example 2:

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] output: 7 There are 7 kinds of possible plans: (0), (1), (2), (0, 1), (0, 2), (1, 2), and (0).Copy the code

Tip:

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• 1 <= group[i] <= 100
• profit.length == group.length
• 0 <= profit[i] <= 100

Dynamic programming

This is a special kind of multi-dimensional cost backpack problem.

Think of each task as an “item,” the number of people needed to complete the task as “cost,” and the profit earned from completing the task as “value.”

Its special lies in the existence of a one-dimensional capacity dimension that needs to be satisfied with “not less than”, rather than the conventional “not more than”. And that requires us to do some equivalent transformation of some states.

define
$f[i][j][k]$To consider before
$i$The number of users does not exceed 1 item
$j$, the profit is at least
$k$Number of schemes.

For each item (starting at 111), we have two choices: select and do not select:

• Optional: There are obviously:

• (j>=group[I −1]j >=group[i-1]j>=group[I −1]), and consider the negative value of “at least profit” : If the “profit dimension” is directly set as K −profit[I −1] k-profit [i-1] K −profit[I −1], negative value may appear. Is the negative value legal? This needs to be combined with the “status definition”. Since it is “the profit is at least KKK”, it belongs to the “legal state” and needs to participate in the transfer. Since we did not design the dynamic gauge array to store the “profit is at least negative weight” state, we need to make an equivalent substitution according to the “state definition” and map this “state” to F [I][j][0] F [I][j][0] F [I][j][0] F [I][j][0]. This is mainly the use of all the task profit is “non-negative”, so it is impossible to appear a negative profit situation, at this time “profit at least a negative KKK” scheme number is actually completely equivalent to “profit at least 000” scheme number.

Finally f[I][j][k]f[I][j][k]f[I][j][k] is the sum of the above two cases.

Then consider the problem of “how to construct effective starting value”, again combined with our “state definition” to consider:

When there are no items (quests), the profit must be 000 (meet at least 000), and there is no requirement for the number of people.

So all f[0][x][0]=1f[0][x][0] =1f[0][x][0] =1.

Code:

class Solution {
    int mod = (int)1e9+7;
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        long[][][] f = new long[m + 1][n + 1][min + 1];
        for (int i = 0; i <= n; i++) f[0][i][0] = 1;            
        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= min; k++) {
                    f[i][j][k] = f[i - 1][j][k];
                    if (j >= a) {
                        int u = Math.max(k - b, 0);
                        f[i][j][k] += f[i - 1][j - a][u]; f[i][j][k] %= mod; }}}}return (int)f[m][n][min]; }}Copy the code

• Time complexity: O(M ∗n∗min)O(M * N * min)O(M ∗n∗min)
• Space complexity: O(M ∗n∗min)O(M * n * min)O(M ∗n∗min)

Dynamic programming (differential method)

The plan was set fast for an hour 🤣

First burst long, and then switch to high precision after being stuck in memory, finally changed to a rolling array after the reluctant (not, steady over, before long is I put N more than a dozen, write 1005, N not wrong words, not rolling is also able to pass 😭😭😭)

The basic idea is to first ignore the minimum minProfit and get all the schemes a only subject to “number restriction”, and then get all the schemes B which consider the “number restriction” and at the same time have a profit lower than minProfit (no more than minprofit-1).

A – B is the answer.

Code:

import java.math.BigInteger;
class Solution {
    static int N = 105;
    static BigInteger[][] f = new BigInteger[2][N]; 
    static BigInteger[][][] g = new BigInteger[2][N][N];
    static BigInteger mod = new BigInteger("1000000007");
    
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;

        for (int j = 0; j <= n; j++) {
            f[0][j] = new BigInteger("1"); 
            f[1][j] = new BigInteger("0"); 
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min; k++) {
                g[0][j][k] = new BigInteger("1"); 
                g[1][j][k] = new BigInteger("0"); }}for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                f[x][j] = f[y][j];
                if(j >= a) { f[x][j] = f[x][j].add(f[y][j - a]); }}}if (min == 0) return (f[m&1][n]).mod(mod).intValue();

        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < min; k++) {
                    g[x][j][k] = g[y][j][k];
                    if (j - a >= 0 && k - b >= 0) { g[x][j][k] = g[x][j][k].add(g[y][j - a][k - b]); }}}}return f[m&1][n].subtract(g[m&1][n][min - 1]).mod(mod).intValue(); }}Copy the code

• Time complexity: first timeDPComplexity of
  $O(m * n)$; The second timeDPComplexity of
  $O(m * n * min)$. The overall complexity is
  $O(m * n * min)$
• Space complexity: O(M ∗n∗min)O(M * n * min)O(M ∗n∗min)

The last

This is the No.879 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.