leetcode 1723. 完成所有工作的最短时间【DFS+剪枝 | 状压DP】

ゝ一世哀愁。 2023-01-19 07:16 28阅读 0赞

**DFS+剪枝**

**超时**

[题解][Link 1]

题解看了一半 学到了用当前得到的最好的结果进行剪枝，但是还是超时  
后来发现当有多个空闲的工人 或者多个工人当前已经总用时相同时重复计算了问题  
因为工人是没有区分的

假设 工人用时是这样的\[0,0,0,0,0,1,1\]  
那么在0和1的这些工人里面调一个开分支即可

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        int ret = INT_MAX;
        vector<int>j;
        int k;
        int minimumTimeRequired(vector<int>& j, int k) { 
            vector<int> p(k,0);
            this->j = j;
            this->k = k;
            dfs(p,0);
            return ret;
        }
    
        bool dfs(vector<int>w,int cur){ 
            int m = 0;
            debug(cur)
            if(cur == j.size()){ 
                int ma = -1;
                for(int i=0;i<w.size();i++){ 
                    ma = max(ma,w[i]);
                }
                ret = min(ret,ma);
                return true;
            }
    
            sort(w.begin(),w.end());
            
            for(int i=0;i< w.size();i++){ 
                if( w[i] + j[cur] < ret){ 
                    w[i]+=j[cur];
                    dfs(w,cur+1);
                    w[i]-=j[cur];
                }
            }
            return true;
        }
    };

> 加入剪枝  
> if(i>0 && w\[i\]==w\[i-1\])\{ continue;\}  
> 即可通过  
> 因为将工人进行了排序 所以直接比较i和i-1即可

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        int ret = INT_MAX;
        vector<int>j;
        int k;
        int minimumTimeRequired(vector<int>& j, int k) { 
            vector<int> p(k,0);
            this->j = j;
            this->k = k;
            dfs(p,0);
            return ret;
        }
    
        bool dfs(vector<int>w,int cur){ 
            
            if(cur == j.size()){ 
                int ma = -1;
                for(int i=0;i<w.size();i++){ 
                    ma = max(ma,w[i]);
                }
                ret = min(ret,ma);
                return true;
            }
    
            sort(w.begin(),w.end());
            
            for(int i=0;i< w.size();i++){ 
                if( w[i] + j[cur] < ret){ 
                    if(i>0 && w[i]==w[i-1]){ 
                        continue;
                    }
                    w[i]+=j[cur];
                    dfs(w,cur+1);
                    w[i]-=j[cur];
                }
            }
            return true;
        }
    };

![在这里插入图片描述][20210508152407369.png]

--------------------

**状态压缩DP**

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
    
        bool print2(int a){ 
            vector<bool>b;
            while(a>0){ 
                b.insert(b.begin(), (a&1) );
                a>>=1;
            }
            while(b.size()<16){ 
                b.insert(b.begin(), 0);
            }
            for(int i=0;i<16;++i){ 
                cout<<b[i]<<" ";
            }
            cout<<endl;
            return true;
        }
        int last1(int n){ 
            if(n==0){ 
                return -1;
            }
            int i=0;
            while(n>0){ 
                if(n&1){ 
                    return i;
                }
                i++;
                n>>=1;
            }
            return i;
        }
        int minimumTimeRequired(vector<int>& j, int k) { 
            int n = j.size();
            vector<vector<int>>dp(k,vector<int>(1<<n,INT_MAX));
            vector<int>sum(1<<n,0);
            
            for(int i=1;i<(1<<n);++i){ 
                int la = last1(i);
                sum[i] = j[la] + sum[i- (1<<la)];
            }
            for(int i=0;i<(1<<n);i++){ 
                dp[0][i] = sum[i];
            }
    
            for(int i=1;i<k;i++){ 
                for(int j = 0;j<(1<<n);j++){ 
                    for(int t = j ;t>0;t = j &(t-1) ){ 
                        dp[i][j] = min(dp[i][j], max( dp[i-1][t], sum[ j - t]));
                    }
                }
            }
            return dp[k-1][(1<<n)-1];
        }
    };

![在这里插入图片描述][20210508174335502.png]

> 取二进制 1111的子集  
> 1 1 1 1  
> 1 1 1 0  
> 1 1 0 1  
> 1 1 0 0  
> 1 0 1 1  
> 1 0 1 0  
> 1 0 0 1  
> 1 0 0 0  
> 0 1 1 1  
> 0 1 1 0  
> 0 1 0 1  
> 0 1 0 0  
> 0 0 1 1  
> 0 0 1 0  
> 0 0 0 1  
> 0 0 0 0

#include <iostream>
    #include <math.h>
    #include <vector>
    
    using namespace std;
    #define debug(x) cout<< #x <<": "<< (x) <<endl;
    
    int maxBit = 4;
    bool print2(int n) { 
        vector<int> b;
        while (n>1){ 
            b.insert(b.begin(),n&1);
            n >>= 1;
        }
        b.insert(b.begin(), n & 1);
    
        while (b.size()< maxBit){ 
            b.insert(b.begin(), 0);
        }
        for (int i = 0; i < b.size(); i++) { 
            cout<< b[i] << " ";
        }
        cout << endl;
        return true;
    }
    
    int main()
    { 
    
        int n = (1 << maxBit);
    
        while (n-- >0){ 
            print2(n);
        }
    
        debug("-----")
        int j = 13;
        int i = 13;
        while (i > 0) { 
            print2(i);
            i = (i - 1) & j;
            
        }
    
        return 0;
    }

**结果**

1 1 1 1
    1 1 1 0
    1 1 0 1
    1 1 0 0
    1 0 1 1
    1 0 1 0
    1 0 0 1
    1 0 0 0
    0 1 1 1
    0 1 1 0
    0 1 0 1
    0 1 0 0
    0 0 1 1
    0 0 1 0
    0 0 0 1
    0 0 0 0
    "-----": -----
    1 1 0 1
    1 1 0 0
    1 0 0 1
    1 0 0 0
    0 1 0 1
    0 1 0 0
    0 0 0 1

> 要是1不挨着，这个时候不能单纯-1  
> 要和原来的数&一下 如13

[Link 1]: https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/gong-shui-san-xie-yi-ti-shuang-jie-jian-4epdd/
[20210508152407369.png]: /images/20221021/70db3d5b815648deaac5344b43afd058.png
[20210508174335502.png]: /images/20221021/d53dca5aa91c4e9d9a6fe90e8653900b.png