[leetcode daily question 2021/5/8]1723. The shortest time to complete all work

The title comes from leetcode, Solutions and ideas represent only personal views . Portal .
difficulty ： difficult （ The idea is right , But I can't think of a way to enumerate subsets quickly , No timeout ）
Time ：-
TAG： Dynamic programming

subject

Give you an array of integers jobs , among jobs[i] Is to complete the first i The time it takes to do this job .

Please assign these jobs to k Workers . All work should be assigned to workers , And each job can only be assigned to one worker . The worker's working hours Is the sum of the time it takes to complete all the work assigned to them . Please design the best work assignment plan , Make the workers Maximum working hours To be able to To minimize the .

Return to the distribution scheme as much as possible Minimum Of Maximum working hours .

Example 1：

 Input ：jobs = [3,2,3], k = 3
 Output ：3
 explain ： Assign each worker a job , The maximum working time is  3 .

Example 2：

 Input ：jobs = [1,2,4,7,8], k = 2
 Output ：11
 explain ： Work is distributed as follows ：
1  Worker number one ：1、2、8（ working hours  = 1 + 2 + 8 = 11）
2  Worker number one ：4、7（ working hours  = 4 + 7 = 11）
 The maximum working time is  11 .

Tips ：

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Ideas

You can see ,1 <= k <= jobs.length <= 12, So this question to flash back It should be solvable .（ But if nothing is done at all , It must be over time （ Because it's a difficult problem ）, So we should also consider the problem of reducing branches ）.

---

If you have done similar problems before , You can know , This is the problem CPU Scheduling problem .

• If you use greedy solution , We can get a better solution in a short time （ But not necessarily the best ）.
• The problem requires the optimal solution , Then it's similar Travel agent problem , Need to use to flash back / Dynamic programming solution .

---

I was thinking about to flash back Namely The top-down + Memorandum The way , So I plan to use Dynamic planning is bottom-up solution （ Faster ？）.
I see... In the back Official answer ( Two points + to flash back + Pruning ), After running for a while, it's still two minutes fast .（ Two points + to flash back 0ms, Kinesiology 500ms）

Dynamic programming

Define an array $dp[i][j]$.
$i$ Show consideration $[0,i]$ Worker number one .$0\le i<k$.
$j$ Indicates the jobs that workers can choose .$0\le j<2^n$.

$j$ Use every representative jobs Selection of .1 For the selection ,0 Is not selected .
For example, in the example 2 in ,$n=5$.
When $j=7$( Binary for 111) Indicated selection jobs[0],jobs[1],jobs[2].
When $j=5$( Binary for 101) Indicated selection jobs[0],jobs[2].

Array $dp[i][j]$ Show consideration $[0,i]$ Worker number one , The available jobs are $j$, Then the minimum maximum working time in the allocation scheme （ Sub problem ）. Final answer $dp[k-1][2^n-1]$ That's what the original topic asked .

For example 1 in ,$n=3,k=3$,$dp[1][5]$ It means there are 2 One worker , The jobs you can choose are jobs[0],jobs[2], Then the minimum and maximum working time in the allocation scheme .
that , Final answer $dp[2][7]$ It's what you want .

---

State transition equation

When only 1 When a worker , We initialize the boundary conditions $dp[0][j]$
$dp[0][j]$ It is equal to the sum of all selected jobs .
$$dp[0][j]=\sum _{i=0}^n(jobs[i]if(2^i\&j)else0)$$

---

about $dp[i][j]$ We need to enumerate number $i$ Worker No. is $j$ Case selection . Enumeration $j$ Subset p.

then , Calculation max( The first $i$ The time spent by worker No , The first $[0,i-1]$ Worker No. is $p$ About $j$ The complement of Spend the minimum time on ).

for example $j=7$.$p=4$ yes $j$ A subset of .$q=3$ yes $p$ About $j$ The complement of .

then , For the first $i$ Each selection of worker No （$j$ Every subset of ）, Let's take a minimum .

---

In short , Current workers $i$ The case that can be selected is $j$, So workers $i$ stay $j$ Pick it up at will , Leave the rest to the workers $[0,i-1]$.

Optimize

There are two optimizations .

1. When you know that the selection is $j$ when , Know quickly $sum={\sum }_{i=0}^n(jobs[i]if(2^i\&j)else0)$ How much is the .

For example, in the example 2 in ,$j=5$,sum = jobs[0]+jobs[2] = 5.

2. Quick enumeration $j$ Subset .

Sum and make a table

For the selection case is $j$, The easiest way is Enumerate $j$ Every one of them , Yes 1 It means choosing . The code is as follows ：

int nbit = pow(2,n);
for(int j=1;j<nbit;j++){
    
	for(int q=0;q<n;q++){
    
	    int mask = pow(2,q);
	    // If the first q Bit is selected （ Selected as 1）
	    if(mask & j){
    
	    	sum += jobs[q];
	    }
	}
}

But this way Time complexity That's it. O($2^n\cdot n$). Is there any way to calculate faster ？

---

We Can you pass the previous calculation , Establish the transfer equation ？
In fact, we observe, for example $j=6$( Binary for 110) when , If 110₂ Change only one , Then we can go through selectJobs[6] = jobs[2] + selectJobs[010₂] perhaps jobs[1] + selectJobs[100₂] obtain .

So can we find a way to change only one digit ？ We need some experience here .
We need to know x & (x-1) What does it mean ？

x & (x-1) Is to eliminate x The lowest of all 1.

that ,y = j - x Is the lowest position eliminated .

for example ,$j=6$
$x=6\&5=110_2\&101_2=4(100_2)$
$y=6-4=110_2-100_2=2(010_2)$

Last , Use Logarithm exchange formula With the y, Got it. jobs The corresponding subscript .

Logarithm exchange formula ：
$$lo{g}_{a}b=\frac{lo{g}_{c}b}{lo{g}_{c}a}$$

int nbit = pow(2,n);
// initialization   The sum of each subset 
vector<int> selectJobs(nbit,0);
for(int j=1;j<nbit;j++){
    
    int x = j & (j-1);
    int y = j - x;
    selectJobs[j] = selectJobs[x] + jobs[log(y)/log(2)];
}

Quickly enumerate each selection $j$ Subset $p$

The simplest solution is , Enumerate again $[1,j]$, If $p\&j>0$ explain $p$ yes $j$ A subset of .

int nbit = pow(2,n);
for(int j=1;j<nbit;j++){
    
	for(int p=1;p<j;p++){
    
	    if(j&p){
    
		    //  If  p  yes  j  A subset of 
		    int sum = selectJobs[p];
		    int not_p_in_j = (~p) & j;
		    int maxTime = max(sum,dp[i-1][not_p_in_j]);
		    dp[i][j] = min(dp[i][j],maxTime);
		}
	}
}

But the time complexity is O($2^n\cdot 2^n$), The wife is slow . Is there any way to calculate faster ？

---

According to the previous x & (x-1) Inspiration of meaning （ In fact, I didn't figure it out ）, In short, you need to enumerate $j$ Subset , Just use the following code ：

//p=0 End of time 
for(int p=j;p;p=(p-1)&j){
    
	//TO DO
}

Code

class Solution {
    
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
    
        int n = jobs.size();
        int nbit = pow(2,n);
        vector<vector<int>> dp(k,vector<int>(nbit,INT_MAX/2));

        // initialization   The sum of each subset 
        vector<int> selectJobs(nbit,0);
        for(int j=1;j<nbit;j++){
    
            int x = j & (j-1);
            int y = j - x;
            selectJobs[j] = selectJobs[x] + jobs[log(y)/log(2)];
        }

        // initialization dp[0][i]
        for(int i=0;i<nbit;i++){
    
            dp[0][i] = selectJobs[i];
        }

        // Start dp
        for(int i=1;i<k;i++){
    
        	// Enumerate the selection 
            for(int j=1;j<nbit;j++){
    
                // enumeration j Subset 
                for(int p=j;p;p=(p-1)&j){
    
                    int sum = selectJobs[p];
                    int not_p_in_j = (~p) & j;
                    //  perhaps  not_p_in_j = j - p;
                    int maxTime = max(sum,dp[i-1][not_p_in_j]);
                    dp[i][j] = min(dp[i][j],maxTime);
                }
            }
        }
        return dp[k-1][nbit-1];
    }
};

Algorithm complexity

Time complexity ： O($k\cdot 3^n$). among n It's an array jobs The length of ,k For the number of workers . We need to O($2^n$) Time preprocessing selectJobs Array . The inner loop complexity is only O($3^n$) instead of O($2^n\cdot 2^n$) = O($4^n$).
Therefore, the time complexity of dynamic programming is O($k\cdot 3^n$), So the total time complexity is O($k\cdot 3^n$).
Spatial complexity ： O($k\cdot 2^n$). among n It's an array jobs The length of ,k For the number of workers . Used to store dp Array .

Official answer dp There can be 500ms, I don't know where it's slow .