钱老板赶工

[编程题]钱老板赶工

热度指数：1798 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

【注意：本题按通过的Case比例给分】

钱老板去国外度了个假，刚回到公司就收到了 n 封催促工作完成的邮件。

每项工作都有完成截止日期 deadline，钱老板做每项工作都会花去cost天，而且不能中断。
请你帮钱老板安排一下完成工作的顺序，以减少总的工作推迟时间。

输入描述:

第一行包含一个正整数 n(1<=n<=20)，表示工作数量。

接下来 n 行，每行包含两个整数，分别表示第 i 项工作的 deadline 和 cost。

输出描述:

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

示例1

输入

输出

说明

输入样例表示有 3 项工作。

第一项工作截止时间在第 3 天，需要 3 天时间完成。

第二项工作截止时间在第 8 天，需要 1 天时间完成。

第三项工作截止时间在第 3 天，需要 2 天时间完成。

因此合理的顺序是 1->3->2 或 3->1->2，均推迟 2 天。

算法知识视频讲解

金际一线天

感谢评论区提供的思路,特地去学习了状态压缩DP的思路,算现学现卖吧

dp[1 << 20] : 保存每个状态下的推迟时间
sum[1 << 20] : 保存每个状态下的花费的天数

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int dp[1 << 20], sum[1 << 20];

int main(int argc, char* argv[]){

    using pair_t = pair<int, int>;
    int n;
    cin >> n;
    vector<pair_t> works(n);
    const int maxn = (1 << n);
    memset(dp, INF, sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i < n; i++) cin >> works[i].first >> works[i].second;
    for(int i = 0; i < maxn; i++){
        for(int j = 0; j < n; j++){
            if(!(i & (1 << j))) {
                int u = i | (1 << j);
                sum[u] = sum[i] + works[j].second;
                dp[u] = min(dp[u], dp[i] + max(0, sum[u] - works[j].first));
            }
        }
    }
    cout << dp[maxn-1] << endl;
    return 0;
}

编辑于 2020-08-07 16:47:45 回复(5)

Python

yQpy.

n=int(input())
a=[]
for _ in range(n): a.append(list(map(int,input().split())))
cache={}
def dfs(d,k):
    if k in cache:return cache[k]
    if k==(1<<n)-1:return 0
    res=1e9
    for i in range(n):
        if 1<<i&k!=0:continue
        res=min(res,dfs(d+a[i][1],k|1<<i)+max(0,a[i][1]+d-a[i][0]))
    cache[k]=res
    return res
print(dfs(0,0))

AC 85%

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int n = 0;
vector<pair<int, int>> a(25);
map<int, int> cache;
int dfs(int d, int k){
	if (cache.find(k) != cache.end()) return cache[k];
	if (k == (1 << n) - 1) return 0;
	int res = 1e9;
	for (int i = 0; i < n; i++){
		if (((1 << i)&k) != 0) continue;
		res = min(res, dfs(d + a[i].second, k | (1 << i)) + max(0, a[i].second + d - a[i].first));
	}
	cache[k] = res;
	return res;
}
int main()
{
	a.clear();
	cache.clear();
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
	cout << dfs(0, 0);
	return 0;
}

AC 90%