Leetcode 1449. Form Largest Integer With Digits That Add up to Target

https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/description/

Notes:

This question belongs to knapsack problem.

Since each element (or digit) can be used as many times as needed, so it is a 01 knapsack problem.

To form the largest number, the first step should find the longest digits that can be formed, this is a typical knapsack problem.

After finding the longest digits that can be formed, we can greedily add the digits from the larger one to the smaller one. 

One of the key condition for the greedy way: 

         dp[target] = 1 + dp[target - cost[i]]

where dp[target] is the length of the longest digits that can be formed.

This equation means that: after taking the largest digit available at this moment, the rest part (target - cost[i]) can still matches the longest digits overall. Thus, it can always give the optimal solution.

See the code below:

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> dp(target+1, -5000);
        dp[0] = 0;
        for(int i=0; i<=target; ++i) {
            for(int j=0; j<9; ++j) {
                if(i>= cost[j]) dp[i] = max(dp[i], 1 + dp[i - cost[j]]);
            }
        }
        if(dp[target]<=0) return "0";
        // cout<<dp[target]<<endl;
        string res = "";
        for(int i=8; i>=0; --i) {
            while(target>=cost[i] && dp[target] == 1 + dp[target - cost[i]]) {
                res.push_back(i+1+'0');
                target -= cost[i];
            }
        }
        return res;
    }
};

Lintcode 564: Backpack VI

https://www.lintcode.com/problem/combination-sum-iv/description

Notes:

As indicated by the title of the question, this problem belongs to backpack or knapsack problems.

But this question does not ask how many ways to fill up the bag, instead, it asks how many combinations to fill up the bag.

Or another way to say this,  the order of picking up one elements does matter!!!

Let say dp[v] represents the ways of combinations to fill it up.

Then,

dp[v] = sum {dp[v - val[i]]}, when v >= val[i].

The meaning is straightforward: we just add another val[i] element at the end of all the previous results. And each of them will still be a unique combination, so it still can be counted as one solution.

The key is that: we must put the first loop as the volume increasing from 1 to v; the inner loop is the elements. This is different from the typical knapsack problem, which is just the opposite.

So what is the difference?

The different is that: if we put the elements in the outside loop, then the order of elements inside the solution does not matter. Or we are calculating how many way to fill up the bag.

This question asks for how may combinations, so we need to pay attention to the relative orders of the elements.

See the code below:

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    int backPackVI(vector<int> &nums, int target) {
        // write your code here
        vector<int> dp(target+1, 0);
        dp[0] = 1; //must have
        for(int i=1; i<=target; ++i) {
            for(int j=0; j<nums.size(); ++j) {
                if(i >= nums[j]) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

To better understand the subtle difference discussed above, we can run a small example: [1, 2], and target = 3.

To this question, the answer is 3. [1, 1, 1], [1, 2], and [2, 1].

If we ask for how many ways to fill-up the bag ignoring the relative orders. then it is 2. [1, 1, 1], and [1, 2].

Leetcode 474: Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/description/

Notes:

This question actually is a typical knapsack problem. More specifically, there are two knapsacks: one is for 1s and the other is for 0s. So it is a 01 two-bags knapsack problem. More details can be found in this post.

See the code below:

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        vector<vector<int>> cts;
        for(auto &a : strs) {
            int n = a.size(), ct = 0;
            for(auto &b : a) {
                if(b == '1') ++ct;
            }
            cts.push_back({n-ct, ct});
        }
        for(int i=0; i<cts.size(); ++i) {
            for(int j=m; j>=cts[i][0]; --j) {
                for(int k=n; k>=cts[i][1]; --k) {
                    dp[j][k] = max(dp[j][k], dp[j-cts[i][0]][k-cts[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

Leetcode 416: Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/

Notes:

This question is a typical 01 knapsack problem. Please refer this post for knapsack problems.

See the code below:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto &a : nums) sum += a;
        if(sum & 1) return false;
        sum >>= 1;
        vector<int> dp(sum+1, 0);
        dp[0] = 1;
        for(int i=0; i<nums.size(); ++i) {
            for(int j=sum; j>=nums[i]; --j) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[sum];
    }
};

The above time complexity is O(N*V), where N is the number of elements and V is the volume or sum.

There is a very inspiring method to record all the possible sum with O(V) time complexity. Using bitset!!!

Based on the definition, bs[idx] can only be two kinds of value: 0 or 1, or false or true. When bs[idx] = =1, means there is a sum == idx.

See the code below:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<50000> bs(1);//initial size and set bs[0] = 1;
        int sum = 0;
        for(auto &a : nums) {
            bs |= bs << a;//all the previous sum + a
            sum += a;
        }
        return !(sum&1) && bs[sum>>1];
    }
};

There is a follow up to this question, please refer to this post.

[Classical Topics 1]: Knapsack Problems

1: 01 knapsack problems

Question description:

        You have a container with volume of V which is used for stones picking up. There are i kinds of stones with only one for each kind, and each have a value of m[i] and volume of v[i], where i is in the range of (0, n]. What is the maximum value can you achieve with your container?

Notes:

This is a 01 knapsack problem. The key logic is: for each stone, we can either choose it or do not choose it. Or yes or no in short.

State transfer equation 1:

             dp[i][v] = max(dp[i-1][v], dp[i-1][v- v[i]] + m[i]),   v>= vi

dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most 1 time (since there is only 1 for each kind). 

Code 1:

int 01kp_2D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
    for(int i=1; i<=len; ++i) {
        for(int j=v[i-1]; j<=V; ++j) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + m[i-1]);
        }
    }
    return dp[len][V];
}

This code can be re-written into one dimensional array:

(why can we do this? If confused, print out the above 2D matrix, and track how dp[i][j] evolves from layer to layer. Pay attention to the relative positions in i and j.)

Code 2:

int 01kp_1D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<int> dp(V+1, 0);
    for(int i=1; i<=len; ++i) {
        for(int j=V; j>=v[i-1]; --j) {
            dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
        }
    }
    return dp[V];
}

2: Complete Knapsack Problems

Question description:

        You have a container with volume of V which is used for stones picking up. There are i kinds of stones, and each have a value of m[i] and volume of v[i], where i is in the range of (0, n]. For each kind of stones, there are infinite number of stones. What is the maximum value can you achieve with your container?

Notes:

This is a complete knapsack problem. The key logic is: for each stone, there are infinite number of them. But actually we have a container with a finite size, V. Thus, for each kind of the stones, the effective number is [V/v[i]]. Now the problem becomes a Multiple Knapsack Problem, which will be covered in the next section. If we treat each stone in the same kind as that in the 01cp, then it is converted to an 01cp.

State transfer equation 2:

             dp[i][v] = max(dp[i-1][v- k*v[i]] + k*m[i]), where v>=vi, 0<= k <= [V/v[i]]

dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most [V/v[i]] times. 

Code 3:

int ckp_2D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
    for(int i=1; i<=len; ++i) {
        for(int k=0; k<=V/m[i-1]; ++k) {
            for(int j=k*v[i-1]; j<=V; ++j) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i-1]] + k*m[i-1]);
            }
        }
    }
    return dp[len][V];
}

Similar to that in 01 Knapsack Problem, we can reduce the space complexity from 2D to 1D. But the time complexity is still O(Len*V*K).

Can we do better?

Let us focus on the volume v, and dp[v] represents the maximum value using a container with volume of v. And for each kind of stones, we can pick up them as many as possible until the container is full.

State transfer equation 3:

             dp[v] = max(dp[v- v[i]] + m[i]),         v>= vi

It seems too simple to be true. 

Let us look at the meaning of the each term. If we know dp[v-v[i]], or with a container with all possible smaller volumes, then dp[v] should be the maximum of all the possible combinations, as illustrated in the above equation. There is no limitation of number of stones for picking up, as long as it can fit in the container. So we can try all the kinds of stones at each layer of volume. Thus, the process of calculation dp[v] should start with smaller v's, or with a bottom-up protocol. This is the key difference between the Complete and the 01 Knapsack Problem.

Code 4:

int ckp_1D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<int> dp(V+1, 0);
    for(int j=1; j<=V; ++j) {//must from smaller v to bigger!
        for(int i=1; i<=len; ++i) {
            if(j>=v[i-1]) dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
        }
    }
    return dp[V];
}

The above two for loops can be switched, 

Code 5:

int ckp_1D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<int> dp(V+1, 0);
    for(int i=1; i<=len; ++i) {
        for(int j=1; j<=V; ++j) {//must from smaller v to bigger!
            if(j>=v[i-1]) dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
        }
    }
    return dp[V];
}

Now let us look at a different way to derive the above ckp result. Let dp[i][v] represent the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up as many times as possible, then

State transfer equation 4:

             dp[i][v] = max(dp[i-1][v], dp[i][v- v[i]] + m[i]),   v>= vi

The only difference between the above equation and that for the 01kp is the second term on the right side of the above equation: here we adopt dp[i][v-v[i]] and in 01kp we use dp[i-1][v-v[i]]. The former means we can use the ith stone to fill v-v[i], now we can use this stone again. The latter means we can only use this stone once. So the former is for the Complete Knapsack Problem, and the latter is for the 01 Knapsack Problem.

Code 6,

int ckp_2D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
    for(int i=1; i<=len; ++i) {
         for(int j=v[i-1]; j<=V; ++j) {
             dp[i][j] = max(dp[i-1][j], dp[i][j-v[i-1]] + m[i-1]);
        }
    }
    return dp[len][V];
}

It is easy to convert it to 1D, which then becomes the same as Code 5!

Code 7, 

int ckp_1D(vector<int> &v, vector<int> &m, int V) {
    int len = v.size();
    vector<int> dp(V+1, 0);
    for(int i=1; i<=len; ++i) {
        for(int j=v[i-1]; j<=V; ++j) {//must from left to right.
            dp[j] = max(dp[j], dp[j-v[i-1]] + m[i-1]);
        }
    }
    return dp[V];
}

3: Multiple Knapsack Problems

The only difference now is that: for each kind of stone, we have known available total number n[i]. Similar to the Complete Knapsack Problem, we can convert it into 01kp. 

State transfer equation 5:

             dp[i][v] = max(dp[i-1][v- k*v[i]] + k*m[i]), where v>=vi, 0<= k <= n[i]

dp[i][v] represents the maximum value using the first i kinds of stones with volume of v and for each kind of stones, we can pick up at most n[i] times. 

Code 8:

int mkp_2D(vector<int> &v, vector<int> &m, vector<int> &n, int V) {
    int len = v.size();
    vector<vector<int>> dp(len+1, vector<int>(V+1, 0));
    for(int i=1; i<=len; ++i) {
        for(int k=0; k<=n[i-1]; ++k) {
            for(int j=k*v[i-1]; j<=V; ++j) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i-1]] + k*m[i-1]);
            }
        }
    }
    return dp[len][V];
}

Can we do better? The answer again is yes! To be continued