アルゴリズムイントロダクション章末問題 15-7 利益最大化スケジュール

1 台の機械に n 個の仕事 a[1], a[2], ..., a[n] の仕事をさせます. 各仕事には処理時間 t[ j ], 利益 p[ j ], 納期 d[ j ] が与えられています. 機械は同時に二つ以上の仕事をすることはできないし, 途中で止めることもできません. 仕事 a[ j ] を納期までに完了すれば利益 d[ j ] が得られます. 納期を越えるとその仕事に対する利益は 0 になります.
利益を最大にしようとスケジュールし, その最大の利益を与えるプログラムを考えます.
ここでは, 1 <= n <= 1000, 1 <= max(d[ j ]) <= 1000 としておきます.

納期きっちりで終わらせる必要はありませんから, 納期の早い順に, そして仕事が納期を越えないように仕事を並べていったときの最大の利益を求めることを考えます. 納期の早い順に仕事をソートしておきます. ここでは a[1], a[2], ..., a[n] がすでに並び替えられていると考えることにします.

最大の納期を dmax, 時刻 t の時点で, 仕事 a[ j ] まで考慮したときの最大の利益を profit[ t ][ j ] とします. profit[ t ][ j ] は, a[j] の仕事をしたときの利益か, しなかったときの利益 (profit[ t-1 ][ j ] と profit[ t ][ j-1]) の中での最大値になります.
仕事 a[ j ] をするには, t[ j ] <= t でないといけません.
また, 納期を越えたら利益 0 ですから, d[ j ] >= t のときだけ, 仕事をする価値があります.

profit[t][j] = max( p[j]+profit[t-t[j]][j-1] if t[j] <=t and d[j] >= t,
                    profit[t-1][j],
                    profit[t][j-1] )

profit[0][k] = 0 (0 <= k <= n)
profit[k][0] = 0 (0 <= k <= dmax)

ソートで O(n*logn) かかり, 上記の漸化式を動的計画法で O(n*dmax) で計算しますから, 全体では O(n*dmax) のアルゴリズムとなります.

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

struct Job {
  int i,t,p,d;
  Job(int i, int t, int p, int d):i(i), t(t), p(p), d(d) {}
  bool operator<(const Job& job) const { return d < job.d; }  
};

int main() {
  int C;
  std::cin >> C;
  for(int c = 1; c <= C; ++c) {
    int n;
    std::cin >> n;
    std::vector<Job> jobs(n+1, Job(0,0,0,0));
    for(int i = 1; i <= n; ++i) {
      int t,p,d;
      std::cin >> t >> p >> d;
      jobs[i] = Job(i,t,p,d);
    }
    std::sort(jobs.begin()+1, jobs.end());

    int profit[1001][1001];
    memset(profit, 0, sizeof(profit));
    int tmax = jobs.back().d;
    for(int t = 1; t <= tmax; ++t) {
      for(int i = 1; i <= n; ++i) {
	int p = 0;
	if(jobs[i].d >= t && jobs[i].t <= t) {
	  p = jobs[i].p+profit[t-jobs[i].t][i-1];
	}
	p = std::max(p, profit[t-1][i]);
	p = std::max(p, profit[t][i-1]);
	profit[t][i] = p;
      }
    }
    std::cout << "Case #" << c << ": " << profit[tmax][n] << std::endl;
  }
}