钱老板赶工

递归和迭代实现, python和C++实现. 方法相同, C++代码通过, python代码超时.

题目链接：https://www.nowcoder.com/questionTerminal/ec64f266f4c44c63a38d3d11024e5230?answerType=1&f=discussion

题目描述:

钱老板去国外度了个假，刚回到公司就收到了 n 封催促工作完成的邮件。每项工作都有完成截止日期 deadline，钱老板做每项工作都会花去cost天，而且不能中断。请你帮钱老板安排一下完成工作的顺序，以减少总的工作推迟时间。

输入描述:

第一行包含一个正整数 n(1<=n<=20)，表示工作数量。
接下来 n 行，每行包含两个整数，分别表示第 i 项工作的 deadline 和 cost。

输出描述:

一个数字，表示钱老板最少需要推迟几天才能完成所有工作。

示例:

• 输入

  3
  3 3
  8 1
  3 2

• 输出:

  2

• 说明
  输入样例表示有 3 项工作。
  第一项工作截止时间在第 3 天，需要 3 天时间完成。
  第二项工作截止时间在第 8 天，需要 1 天时间完成。
  第三项工作截止时间在第 3 天，需要 2 天时间完成。
  因此合理的顺序是 1->3->2 或 3->1->2，均推迟 2 天。

分析

假设有N项工作, 编号为1,2,...,N; 那么一定存在一个完成工作的序列, 按照这个序列完成所有工作, 推迟的天数最少.
假设我们已经完成了K项工作, 剩余M=N-K项工作, 那么怎么安排剩余的M项工作, 使得这M项工作超期的天数之和最小呢?
假设K项工作耗时为previous_cost, 在剩余的M项工作中任意选择一项, 假设其编号为i, 其耗时为costs[i], 截止日期为deadlines[i], 那么剩余的M-1项工作就构成了一个子问题:
已经完成K+1项工作, 已经耗时previous_cost+costs[i], 剩余M-1项工作, 求一个最佳序列使得这M-1项工作超期天数最小.

看到这里已经基本清楚了, 对于初始的情况, 已完成的工作为0, previous_cost=0, 剩余工作集合work_set大小为N.
我们将所有的工作按照输入的顺序进行编号, 假设为{1,2,...N}, 那么我们要求的问题可以归纳为, 从时刻0开始, 剩余的工作集合work_set={1,2,...,N}, 求最少的推迟时间.

• 划分子问题
  假设有这样一个函数dp, 给它输入起始时间, 还有剩余的工作编号的集合, 它就能自动返回最优的结果.

  def dp(t_start, work_set):
    ## 黑盒
    return minimal_postpone        ## 返回最小推迟时间

  那么我们是不是只要返回 dp(0, work_set)就行了? 当然不行, 继续往下看.
  我们可以将问题分解, 从work_set中任意抽取一项工作 i, 只计算它的推迟时间:postpone_i, 然后将剩余的工作的集合work_set-{i}扔给dp函数计算, 得到postpone_remain, 那么postpone_i+postpone_remain就是完成work_set中所有工作的一个推迟时间, 但是不一定时最优的, 必须遍历整个集合进行比较. 于是有以下代码:

  def dp(t_start, work_set):  
    postpone_min = INT_MAX  
    for i in workset:  
       postpone_remain = dp(0+cost[i], workset-{i})        ## 计算剩余N-1项工作的最优解
       postpone_i = max(costs[i]-deadlines[i],0)            ## 计算工作i的推迟时间, 如果没有推迟, 那就是0
       postpone_min = min(postpone_min, postpone_i+postpone_remain)    ## 记录最小的推迟时间

  但是一直递归肯定有问题, 我们必须指定终止条件. 显然, 当work_set为空时, 自然应该停止. 那么为空时返回什么值呢? 返回0, 因为没有工作, 自然也没有推迟.
  ```
  def dp(t_start, work_set):
  if 0 == len(work_set):

    return 0

  postpone_min = INT_MAX
  for i in workset:

   postpone_remain = dp(0+cost[i], workset-{i})        ## 计算剩余N-1项工作的最优解
   postpone_i = max(costs[i]-deadlines[i],0)            ## 计算工作i的推迟时间, 如果没有推迟, 那就是0
   postpone_min = min(postpone_min, postpone_i+postpone_remain)    ## 记录最小的推迟时间

• 时间复杂度优化, 使用备忘录
  现在代码逻辑上是没有什么问题了, 但是代码的效率却堪忧. 聪明人一眼可以看出来, 它本质上是将长度为N的序列进行了全排列, 然后求每个排列的推迟时间, 时间复杂度为O(N!). 那么怎么优化呢? 学过动态规划的一定知道一个东西叫做备忘录memo, 它可以解决递归过程中的大量重复计算问题. 就是说, 某一个子问题被重复计算了多次.
  比如在这个问题中, 假设剩余的工作集合为{1,2,3,4}, 那么它被分为四个子问题{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}; 在解决子问题{1,2,3}时, 会解决掉子问题{1,2},{1,3},{2,3}, 但是在解决子问题{1,2,4}时, 又会重复计算{1,2}, 在解决子问题{1,3,4}时, 会再一次计算{1,3}. 类似的重复计算的数量时惊人的.
  这时候备忘录就很有用了, 备忘录一般情况下是一个哈希表, 它可以将你计算过的子问题和结果以(key,value)的形式记录下来. 每当你计算一个问题时, 可以先访问这个备忘录, 如果有结果, 直接返回即可.
  这样的话, 这个问题的时间复杂度变成了. 原因是, 我们将排列问题变成了组合问题: 已经计算过的集合{}, 一定已经是最优的了. 那么从问题规模从N到1, 子问题的数量总和为, 因此时间复杂度为. 空间复杂度同样为, 因为每个子问题都需要记录到哈希表中.

• 进一步优化
  通常带备忘录的递归方法, 可以改为迭代的方式, 这样可以节省下递归调用栈压栈的开销, 而且也能避免超过系统允许的调用栈深度.
  具体看代码即可.

代码

C++ 带备忘录递归, 通过

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

struct Args{
    int N;
    int* deadlines;
    int* costs;

    Args(int N, int* deadlines, int* costs):N(N),deadlines(deadlines),costs(costs){
    }
};

int recur(Args &args, int previous_costs, int code, vector<int>& memo){
    if(memo[code] != INT_MAX)
        return memo[code];

    int postpone_min = INT_MAX;
    int current_postpone = 0;
    int future_postpone = 0;
    int mask = 0;
    int i = 0;
    while(i<args.N){
        mask = 1<<i;
        if((mask&code) != 0){
            current_postpone = max(previous_costs + args.costs[i] - args.deadlines[i], 0);
            future_postpone = recur(args, previous_costs + args.costs[i], code-mask, memo);
            postpone_min = min(postpone_min, current_postpone + future_postpone);
            // cout<<"code:"<<code<<" previous_costs:"<<previous_costs<<" current_postpone:"<<current_postpone<<" future_postpone:"<<future_postpone<<" postpone_min"<<postpone_min<<endl;
        }
        i += 1;
    }

    memo[code] = postpone_min;
    return postpone_min; 

}

int main(){
    int N = 0;
    int deadlines[20] = {0};
    int costs[20] = {0};
    cin >> N;

    for(int i=0; i<N; ++i){
        cin>>deadlines[i]>>costs[i];
    }

    Args args(N, deadlines, costs);

    vector<int> memo(1<<N, INT_MAX);
    memo[0] = 0;

    int postpone = recur(args, 0, (1<<N)-1, memo);
    cout << postpone <<endl;

    return 0;
}

C++迭代, 通过

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>

using namespace std;

vector<int> get_combination(int k, int L, int H);
int sum(vector<int>& costs, int combination);

int main(){
    int N = 0;
    int TOTAL_COST = 0;
    cin >> N;

    vector<int> deadlines(N, 0);
    vector<int> costs(N, 0);

    for(int i=0; i<N; ++i){
        cin>>deadlines[i]>>costs[i];
        TOTAL_COST += costs[i];
    }

    vector<int> dp(1<<N, INT_MAX);
    dp[0] = 0;

    vector<int> combinations;
    int previous_cost = 0;
    int comb_copy = 0;
    int bi_index = 0;
    int i = 0;
    int postpone_i = 0;

    for(int k = 1; k<=N; ++k){
        combinations = get_combination(k, 0, N-1);
        for(auto combination:combinations){
            previous_cost = TOTAL_COST - sum(costs, combination);
            comb_copy = combination;
            while(comb_copy){
                bi_index = comb_copy&(-comb_copy);
                i = round(log(bi_index)/log(2));
                postpone_i = max(previous_cost+costs[i]-deadlines[i], 0);
                dp[combination] = min(dp[combination], postpone_i+dp[combination-bi_index]);

                comb_copy -= bi_index;
            }
        }
    }

    cout << dp[(1<<N)-1] <<endl;

    return 0;
}

/*
返回从[L,H]区间抽取k个数字的所有组合, 当然每个组合都是一个数字, 它表示的组合是在二进制表示中有k个1, 比如0b0101, 这是一个k为2的组合,
它的十进制数是5
*/
vector<int> get_combination(int k, int L, int H){
    if(k==0){
        vector<int> combinations(1, 0);
        return combinations;
    }
    if(k>=1){
        vector<int> combinations;
        vector<int> sub_combnations;
        for(int i=L; i<=H-k+1; ++i){
            sub_combnations = get_combination(k-1, i+1, H);
            for(vector<int>::iterator iIter = sub_combnations.begin(); iIter!= sub_combnations.end(); iIter++){
                *iIter += 1<<i;
            }
            combinations.insert(combinations.end(), sub_combnations.begin(), sub_combnations.end());
        } 
        return combinations;
    }
}


int sum(vector<int>& costs, int combination){
    int cum = 0;
    while(combination){
        auto bi_index = combination&(-combination);
        auto i = round(log(bi_index)/log(2));
        cum += costs[i];
        combination -= bi_index;
    }
    return cum;
}

python, 带备忘录的递归, 超时, 通过率80%

import sys

## 处理输入
N = int(sys.stdin.readline().strip())
deadlines = []
costs = []
for _ in range(N):
    deadline, cost = list(map(int, sys.stdin.readline().strip().split()))
    deadlines.append(deadline)
    costs.append(cost)

## 递归
memo = {}
def recur(t_start, seq):
    ##终止条件
    if len(seq) == 0:
        return 0
    else:  
        ## seq是set类型, 不能直接哈希, 先转为tuple类型
        key = tuple(seq)        
        if key in memo:
            return memo[key]

        T_min = float('inf')
        ## 遍历所有情况
        for i in seq:
            t_i = t_start+costs[i]
            Ti = max(t_i-deadlines[i],0)
            ## 求解子问题
            T_rem = recur(t_i, seq-{i})
            T_min = min(T_min, Ti+T_rem)
        memo[key] = T_min
        return T_min

## 调用递归函数, 输出结果    
seq = set(range(N))
postpone = recur(0, seq)
print(postpone)

python, 迭代法, 超时, 通过率85%

import sys
from itertools import combinations

## 处理输入
N = int(sys.stdin.readline().strip())
deadlines = {}
costs = {}
TOTAL_COST = 0

## 对工作进行编号, 为了方便组合, 第i个工作的编号为1<<i位, 这样N位大小的数字可以表示所有的组合;
##  比如N=3, 二进制0b111表示工作集合{1,2,3}, 0b011表示工作集合{1,2}; 从集合中去掉某一项工作也很简单, 
## {1,2,3}-{1}可以表示为0b111-0b001=0b110, 即7-1=6.
for i in range(N):
    deadline, cost = list(map(int, sys.stdin.readline().strip().split()))
    deadlines[1<<i] = deadline
    costs[1<<i] = cost
    TOTAL_COST += cost

## 所有工作的集合
workset = [1<<i for i in range(N)]
## dp数组, 大小为2^N, 初始值设置为可能的最大推迟时间
dp = [TOTAL_COST]*(2**N)
## 没有工作时, 推迟时间为0
dp[0] = 0

## 问题规模从小到大, 从1项工作的组合, 到N项工作的组合
for k in range(1,N+1):
    for combination in combinations(workset, k):
        code = sum(combination)
        previous_cost = TOTAL_COST-sum([costs[i] for i in combination])
        for i in combination:
            dp[code] = min(dp[code], max(previous_cost+costs[i]-deadlines[i],0)+dp[code-i])

print(dp[(1<<N)-1])