5639. 完成所有工作的最短时间

5639. 完成所有工作的最短时间

类似：
410. 分割数组的最大值：这个是要求子数组，不是子集

dfs

这样写是k!的。
相比于纯暴力算法，这样的写法是：如果s中有多个空的（0），不需要全都试一遍
纯暴力的复杂度是k**n

class Solution {
public:
    vector<int> jobs;
    vector<int> s;
    int res = INT_MAX;

    void dfs(int u, int b, int c) {
        if (c > res) return;
        if (u >= jobs.size()) {
            res = c;
            return;
        }

        for (int i = 0; i < b; i++) {
            s[i] += jobs[u];
            dfs(u + 1, b, max(c, s[i]));
            s[i] -= jobs[u];
        }

        if (b < s.size()) {
            s[b] = jobs[u];
            dfs(u + 1, b + 1, max(c, s[b]));
            s[b] = 0;
        }
    }

    int minimumTimeRequired(vector<int> &_jobs, int k) {
        s=vector<int>(k);
        jobs = _jobs;

        dfs(0, 0, 0);
        return res;
    }
};

状态压缩dp

题解写的挺好的

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n=jobs.size();
        vector<int>tot(1<<n,0);
        int dp[k][1<<n];
        memset(dp,0,sizeof dp);
        
        // 预处理出tot[i]
        // tot[i]：子集 i 的总工作时间
        for(int i=0;i<(1<<n);i++){
           for(int j=0;j<n;j++){
               if((i&(1<<j))==0)continue;
               tot[i]=tot[i-(1<<j)]+jobs[j];
           }
        }
        for(int i=0;i<(1<<n);i++){
            dp[0][i]=tot[i];
        }
        // j表示前j个工人
        for(int j=1;j<k;j++){
            // 遍历所有集合 i
            for(int i=0;i<(1<<n);i++){
                int mn=INT_MAX;
                //  遍历集合 i 的子集
                for(int s=i;s;s=(s-1)&i){
                    int tmp=max(dp[j-1][i-s],tot[s]);
                    mn=min(tmp,mn);
                }   
                dp[j][i]=mn;
            }
        }

        return dp[k-1][(1<<n)-1];
    }
};

状压dp+二分

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n=jobs.size();
        vector<int>tot(1<<n);
        for(int i=0;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if(i&(1<<j)){
                    tot[i]=tot[i-(1<<j)]+jobs[j];
                    break;
                }
            }
        }

        int l=0,r=0;
        for(auto i:jobs){
            r+=i;
            l=max(l,i);
        }

        while(l<r){
            int x=(l+r)>>1;
            // dp[i] : 处理集合为 i 的工作，需要最少员工的数量
            int dp[1<<n];
            memset(dp,0x3f,sizeof dp);
            dp[0]=0;  // 处理集合为0需要0个员工
            for(int i=0;i<(1<<n);i++){
                for(int s=i;s;s=(s-1)&i){
                    if(tot[s]<=x){
                        dp[i]=min(dp[i],dp[i-s]+1);
                    }
                }
            }
            if(dp[(1<<n)-1]<=k)r=x;
            else l=x+1;
        }
        return l;
    }
};