钱老板赶工
钱老板赶工
https://www.nowcoder.com/questionTerminal/ec64f266f4c44c63a38d3d11024e5230
递归和迭代实现, 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])
投递菜鸟集团等公司10个岗位