調達DXを担う部署で働いているFRくん、今日は嬉しい休日です！
ポカポカ陽気にうつつを抜かし、二度寝しようとした矢先、妻のPRODさんから今日は家族サービスデーの日だと告げられてしまいました。普段はPCの前にしかいないFRくん、今日こそは頑張らなくてはなりません。意気揚々と布団から出たFRくんはまず、お皿洗いの所要時間を計算するためのプログラムを書くことにしました。
FRくん夫妻は料理好きなので、様々な料理を作ります。たくさんの食器を洗うために、FRくん宅のシンクは2台並んで配置されているので、片方のシンクでお皿を洗う間、もう片方のシンクでもお皿を洗うことができます。
FRくん夫妻は手分けしてお皿を洗うことにしました。つまり、片方のシンクでFRくんがお皿を洗い、もう片方のシンクでPRODさんがお皿を洗います。
状況をまとめると以下になります。
FRくん夫妻はお皿洗いをします。洗わなければいけないお皿が 
枚、それぞれのお皿を洗う時間が各
分であるとき、2台のシンクで全てのお皿を洗い終わるまでの所要時間は最速で何分でしょうか？ ただし、お皿が大きいので2人とも1枚ずつしかお皿を洗えず、両者のお皿を洗う能力は同じであるとします。
具体例を考えてみましょう。お皿が6枚あり、それぞれの洗う時間を以下の場合を仮定します。
| お皿 | 洗うのにかかる時間 A (分) |
| 1 | 2 |
| 2 | 4 |
| 3 | 5 |
| 4 | 3 |
| 5 | 3 |
| 6 | 3 |
まずは手計算をしてみます。FRくんがいくつかのお皿を選んで洗う時、PRODさんは残りのお皿を洗うことになります(★)。例えば1,2,3のお皿をFRくん、4,5,6のお皿をPRODさんで洗う時、FRくんの所要時間は11分、PRODさんの所要時間は9分になるため、全てのお皿を洗い終わる時間は11分となります。
まだ洗っていないお皿のうち、洗うのにかかる時間が短い順に洗っていくことを考えてみましょう。そうすると、FRくんは1→5→2の順番で洗って計9分、PRODさんは4→6→3の順番で洗って計11分かかるので、全てのお皿を洗い終わるまでにかかる時間は11分となります。
FRくんがお皿1,3,4、PRODさんが2,5,6を洗う場合はどうでしょうか？
この時、FRくんの所要時間は10分、PRODさんの所要時間も10分になるため、全てのお皿を洗い終わる時間は10分となります。
実はこれが、全てのお皿を洗い終わる最速時間になります。
上記の場合、「そのお皿をどちらが洗うか？」を全探索すれば答えが求まります(全部で
通り)。この場合の計算量は
です。しかし、今回のお皿は最大で100枚になることもあります。この場合の通り数は大変大きな数字となってしまう(1,267,650,600,228,229,401,496,703,205,376通り！)ため、愚直に計算すると大きな計算コストがかかってしまいます。そうなってしまうと、計算機で高速に計算することができません。FRくんは困ってしまいました。
ところでFRくんは先日、社内の勉強会で「動的計画法」を知りました。動的計画法とは、部分問題の結果を用いることで、対象となる問題を解いていく手法のことです。
あの勉強会はすごく面白かったなぁと回想していると、ふと「部分和問題」を思い出しました。部分和問題とは、N個の数字が与えられたとき、その中からいくつか選んで和をXにできるか？ という問題のことです。
ここでFRくんは、(★)で思いついた考察によって、「FRくんが洗うお皿をいくつか選び、それらを洗い終えるための所要時間がX分の時、PRODさんがお皿を洗う時間は(全てのお皿を洗う時間の総和) – Xと書ける」ことに気が付きました。
部分和問題は一般にNP完全ですが、お皿を洗う時間の総和は最大で1,000,000分程度であることを考えると、今回のXは動的計画法を用いることで計算できそうです。この場合、計算量は
になります。
FRくんは、C++言語を用いて上記のように動作するプログラムを作成しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <vector> #include <numeric> constexpr int LIMIT = 100100; // 所要時間の最大値より大きい値とする constexpr int D_MAX = 110; // 100以上の値を設定する int n, sum, ans; std::vector<int> t; std::vector<std::vector<int>> dp(D_MAX, std::vector<int>(LIMIT, 0)); // dp[i][j]:= i番目までのお皿をj[分]で洗えるか？(できる=1, できない=0) int main() { std::cin >> n; t.resize(n); for (int i = 0; i < n; i++) { std::cin >> t[i]; } sum = std::accumulate(t.begin(), t.end(), 0); // 時間の総和 for (int i = 0; i < D_MAX; i++) { dp[i][0] = 1; // 0分はどのような場合でも達成可能 } for (int i = 0; i < n; i++) { for (int j = 0; j <= LIMIT; j++) { // i+1番目のお皿を選択しない場合 dp[i + 1][j] |= dp[i][j]; if (j + t[i] <= LIMIT) { // i+1番目のお皿を選択する場合 dp[i + 1][j + t[i]] |= dp[i][j]; } } } ans = LIMIT; for (int i = 0; i <= sum; i++) { // 答えの集計 ans = (dp[n - 1][i] && sum - i >= 0) ? std::min(ans, std::max(sum - i, i)) : ans; } std::cout << ans << std::endl; } |
前述の例において上記プログラムを動作させた場合、40ms程度と高速に計算することができます。この時、dp配列の各要素には計算結果が格納されています。
実際のFRくん夫妻のシンクには、合わせて40枚ほどのお皿が積みあがっていました。現実は非情です。FRくんは、たくさんのお皿に一瞬たじろいだものの、作成したプログラムを使用することにより、1時間程度でお皿を洗い終わることが分かりました。思ったより時間がかからないことが分かったFRくんとPRODさんは、気合を入れてお皿洗いを完了させました。家族サービスデーの大役を務めたFRくんは、また布団に入っていきました。。。
ある問題においてプログラムを作成するとき、その性質を調べることで計算量の改善ができることがあります。このような場面は業務で取り組むタスク以外だけでなく、例えば日常生活のワンシーンにも潜んでいます。ここまで読んで下さった皆さんの周りにも、きっと存在します。探してみてくださいね。