問題設定
\(n\)個の会社それぞれに、エンジニアの人数\(q\)と価格\(r\)が与えられる
会社をいくつか選んで契約した時に、エンジニアの人数の合計がある値\(m\)以上になるときの最小のコスト(価格の合計)を求める
ただしそれぞれの会社の人数の一部だけを雇うことはできず、会社ごとにまとめて契約することしかできない
解法1 - 動的計画法
どうみてもナップザック問題だ!ということで動的計画法を書いてみたところテストケース7で3.5秒ぐらいかかってしまいました
計算量は\(O(mn)\)ぐらい
m = input() n = input() qr = [map(int, raw_input().split()) for i in xrange(n)] MAX = n * 10000 + 20000 MAX2 = n * 10000 dp = [5000000 * 100] * (MAX + 1) dp[0] = 0 qr.sort(key=lambda x: float(x[1]) / x[0]) result = 5000000 * 100 candidate = set([0]) for i in xrange(n): new = set() next = dp[:] for j in candidate: t = dp[j] + qr[i][1] k = j + qr[i][0] if next[k] > t: next[k] = t if k >= m and result > t: result = t if k <= MAX2 and next[k] < result: new.add(k) candidate |= new dp = next print result
解法2 - 深さ優先探索 + 枝刈り
Pythonで最速のコードは0.01秒とのことなので、↑のコードを参考にしつつ深さ優先探索と枝狩りのコードを書きました
普通に深さ優先探索すると非常に時間がかかるけど、途中で必要ない探索を打ち切ることで高速に計算できる
こっちの方法は簡単に0.01秒を達成できます
枝刈りでどれぐらい計算量が減るのか見積もりが難しいし、最悪の場合はこっちのほうが動的計画法よりも重そうな気がしないでもないですが……
こっちの方法で重要なのは枝刈りに使うためのコストの下限を求めることです
一人あたりの単価が小さい順に会社をソートしておくことで、順番に足していけば必要な人数分のコストの下限が計算できます。
ただし人数が丁度にならない場合があるので、その場合は半端な人数分の価格を足します
たとえば、残り必要な人数が150人の時、100人で価格1000と100人で価格500の会社があるなら、単価の安い価格500の方から100人、価格1000の方から50人分で\(500+1000 \times \frac{50}{100}=1000\)として計算します
端数も含めて効率のよい会社から順にコストを計算しているので、ここで計算した合計のコストは最終的に求めるべきコストと等しいか、それよりも小さくなります(下限)
これにより計算途中で、現在までの最小値とコストの下限を比較して、下限が最小値よりも大きい場合には最小値を下回る可能性がないので探索を打ち切ることができます
コストの下限の計算は下のコードではlower_bound関数で行っています
メモ化もしているので多少速くなっていると思います(何もしないでも0.01秒でしたが
m = input() n = input() company = [] for i in xrange(n): q, r = map(int, raw_input().split()) company.append((float(r) / q, q, r)) company.sort() best = [5000000 * 50] class memoize(dict): def __init__(self, func): self.func = func def __call__(self, *args): return self[args] def __missing__(self, key): result = self[key] = self.func(*key) return result @memoize def lower_bound(i, rest): unit, num, price = company[i] cost = price if rest >= num else rest * unit rest -= num if rest <= 0: return cost elif i + 1 >= n: return 100000000 else: return cost + lower_bound(i + 1, rest) @memoize def dfs(i, rest, cost): rest_new = rest - company[i][1] cost_new = cost + company[i][2] if rest_new <= 0: if best[0] > cost_new: best[0] = cost_new elif i + 1 < n and best[0] >= cost + lower_bound(i + 1, rest_new): dfs(i + 1, rest_new, cost_new) if i + 1 < n and best[0] >= cost + lower_bound(i + 1, rest): dfs(i + 1, rest, cost) dfs(0, m, 0) print best[0]