CS6.006 Problem Set 7を解く

CS 6.006 Problem Set

今回で最後のPSet。

問題はこちら 意訳が間違っていたらご指摘ください。

7-1

DPを実装する問題。漸化式が与えられているので境界条件に注意してコードする。 また、遷移した親のアドレスも保持する必要がある。

7-2

会社の株価の過去データが与えられている。 1991年に買い、2011年に売るとして、もっとも儲けられる組み合わせを探す。

会社 株価(1991) 株価(2011)
Dale 12 39
JCN 10 13
Macroware 18 47
Pear 15 45

(a): 20ドルもっていた場合の最適な買い方は？

複数の株を同時に買うお金がないので、どれか一つ買えばよい。

  • Dale: 39 + (20 - 12) = 47
  • JCN: 13 + (20 - 10) = 23
  • Macroware: 47 + (20-18) = 49
  • Pear: 45 + (20 - 15) = 50

よってPearを一つ買えばok→正解。

(b): 30ドルもっていた場合の最適な買い方は？

複数の株を同時に変えるので組み合わせが多くなる。気をつける。以下の場合がある。

  • (Dale, Dale): 39 + 39 + (30 - 12 - 12) = 84
  • (Dale, JCN): 39 + 13 + (30 - 12 - 10) = 60
  • (Dale, Macro): 39 + 47 + (30 - 12 - 18) = 86
  • (Dale, Pear): 39 + 45 + (30 - 12 - 15) = 87
  • (JCN, JCN, JCN): 39 + (30 - 10 - 10 - 10) = 39
  • (JCN, Macro): 13 + 47 + (30 - 10 - 18) = 62
  • (JCN, Pear): 13 + 45 + (30 - 10 - 15) = 63
  • (Pear, Pear): 45 + 45 + (30 - 15 - 15) = 90

よってPearを二つかえばok→正解。

(c): 120ドルもっていた場合の最適な買い方は？

組み合わせを全部考えると大変なことになるので、サボる。 (b)から、30ドル買った時の最適な買い方はPearを二つ買うことなので、Pearを8つ買えば良さそうに見えるが、 倍率的にDaleがもっとも高いので、現金が余らずに買えるときはDaleをなるべく買えば良いことがわかる。よって、 Daleを10株買えば良い。儲けはPearを8つ買うより、390 - 45 * 8 = 30多い。→正解。

次に、codingに関する条件が加わる。 用意される変数は以下の通り。

変数 役割
total 持ち金
count 会社の数
start 1911年の株価が入っている配列
end 2011年の株価が入っている配列

以下ではナップザック問題との違いを考える設問が続く。 ナップザック問題の変数は以下の通り。

変数 役割
items アイテムの数
size 各アイテムの大きさが入っている配列
value 各アイテムの価値
capacity ナップザックの容量

(d): この問題の変数であるtotalに対応するナップザック問題の変数は？

capacity→正解。

(e): この問題の変数であるcountに対応するナップザック問題の変数は？

items→正解。

(f): この問題の変数であるstartに対応するナップザック問題の変数は？

size→正解。

(g): この問題の変数であるendに対応するナップザック問題の変数は？

(最大化したいので)value→正解。

(h): ナップザック問題がこの問題にそのまま適用できない理由としてTrue/Falseを答えよ。

まず騙されたと思ってナップザックが使えると考えてみて、漸化式を作ると、

dp[i][j]: i番目の株までみて、残りj円である時の最大利益 dp[i+1][j] = max(dp[i][j], dp[i][j+start[i]] + end[i])

ここで、株は一個以上買うこともできるので、何個買ったかの情報も欲しい。 また、実際の最大利益は、値上がり後の株価(end)だけじゃなく、余ったお金も足さないといけない。

問題の選択肢に戻る。以下は選択肢と自分の判断根拠。

1: この問題では、買う時と売る時の間に時間差があるから。

→時間差は現実的にはあるが、問題と関係ない。というかナップザックもつめたアイテムを後で売ると考えれば時間差がある。

2: この問題で扱う数字はintegerであるが、ナップザック問題におけるvalueの数字はintegerではないから。

→ 数が大きいだけなら配列の大きさを適切に大きくすれば良いだけなので理由にならない。

3: この問題では、余ったお金も利益に考慮しなければならないので、答えが無限大となる可能性がある。ナップザック問題にはこのような欠点を扱う概念がない。

余ったお金も利益に足していると、漸化式が計算されるたびに残金が加算されていくので、無限大になる可能性がある。よって理由として正しい。

4: ナップザック問題でいうsizeにあたる変数がこの問題にはない。

→: 購入時の価格がsizeにあたるので理由として間違っている。

5:この問題では二つ以上の株が買えるから

→: ナップザック問題でも二つ以上のitemが入れられる場合を考慮できるので、理由として間違っている。と思ったが、シンプルなナップザック問題のアルゴリズムが適用できない理由としては正しいのでは。

6: この問題では、買った株を全て売る必要がある。ナップザック問題ではそのようなことをする必要がないから。

→: endは2011年の株価だが、これからstartを引いて利益分だけ表す配列にすれば対応できる。よって理由にはならない。

→正解。(3と5がonly valid reasonと書いてある)

以下では、この問題を解くプログラムが与えられる。このプログラムは2つの関数からなり、1つ目の関数の実装として2通り、2つ目の関数の実装として3通りが考えられる。合計で5種類の関数が与えられる。(一つ一つの関数が長いので詳細はPDFを参照してください。)

  • stock-table-A (dpテーブルを埋めている)
  • stock-table-B (同上) -stock-result-A -stock-result-B -stock-result-C

以下では時間計算量を答える。

(i): stock-table-Aの最悪時間計算量は？

purchase[cash][stock]: 残金cashでstockが与えられている時、買うか買わないかを表す(True/False)。

\Theta(count*total)→正解。

(j): stock-table-Bの最悪時間計算量は？

一つ前の設問と同じ。 \Theta(count*total)→正解。

(k): stock-result-Aの最悪時間計算量は？

\Theta(count)→正解。

(l): stock-result-Bの最悪時間計算量は？

\Theta(count)→正解。

(m): stock-result-Cの最悪時間計算量は？

\Theta(count + total)

(n): stock-table-Aで行われる計算を式で書くと？

9-14行目の内容を式一つで表せば良い。

profit[cash, stock] = max(profit[cash, stock-1], profit[cash-start[stock], stock] + end(stock))

一番これっぽい選択肢は、5番目の選択肢。→正解。

(o): stock-table-Bで行われる計算を式で書くと？

profit[cash, stock] = max(profit[cash, stock-1], profit[cash-start[stock], stock-1] + end(stock))

一番これっぽい選択肢は、2番目の選択肢。→正解。

stock-table-Aとstock-table-Bの漸化式は、わずかに違うが、Aは同じ株を複数回買える時の漸化式で、Bは株が一度しか買えない場合の漸化式となっていて、 全く違う。

設問(n): なぜこうなるか？

同じ株を何回も買えるという要素を含めて漸化式を書くところから始まる。

dp[i][j] = max(dp[i-1][j - ks[i]] + kend[i]) ... (j - k*s[i] >= 0となるような全てのk)

つまり、s[i]を0個, 1個, ..., ○個買う場合を考えて、その中から最大値を取ってくる操作である。こっちの漸化式は理解しやすいと思う。 で、これをそのまま実装するとk回のforループが回り効率が悪いので、なんとか時間短縮する為に、この漸化式を簡単にする必要がある。 ここで、dp[i][j-S[i]]は、dp[i][j]よりも先に計算されることに注目する。

dp[i][j-s[i]] = max(dp[i-1][j-ms[i]] + mend[i]) ... (j - m * s[i] >= 0となるような全てのm)

先ほど、dp[i][j]の更新でk = 0, 1, 2, ...と試す、という記述をした。つまりdp[i-1][j], dp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の状態をみている。 このうち、二つ目以降であるdp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の部分は、dp[i][j-s[i]]の更新において、m=1, 2, ..., の状態をみることに等しい。 つまり、dp[i][j-s[i]]は、dp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の最大値がすでに計算されているのだ。

なので、dp[i][j]は、dp[i][j-s[i]]と、足りてないdp[i-1][j]のうち大きい方を取ることで正しく計算できる。 これを表したのが、設問nのような式である。

以上。

--

(p) 5つのアルゴリズムの組み合わせのうち、どの組み合わせがナップザック問題への正しいプログラムになるか？

stock-table-Bは同じ商品を一度しか選ばない漸化式に基づいている。また、stock-result-Aも同じである。 よって, stock-table-Bとstock-result-Aの組み合わせが正しい。

→不正解。stock-table-Bとstock-result-Bの組み合わせが正しい。 stock-result-Aはpurchaseの値をそのまま株数に加算していて、integerとして扱っているが、実際に計算されるpurchase配列にはbooleanの値が入っている。 よってpurchaseの中身をintegerではなくbooleanとして扱っているstock-result-Bが適切とのこと。自分の不注意で間違えた。(Pythonならstock-result-Aもちゃんと動くと思うので自分の選択肢でも間違ってないと思うが。。。)

(q) 5つのアルゴリズムの組み合わせのうち、どの組み合わせがこの株価問題への正しいプログラムになるか？

stock-table-Aは同じ商品を複数回買える漸化式に基づいている。また、stock-result-Cのみが同じ商品を複数回買えることを表している。 よって、stock-table-Aとstock-result-Cの組み合わせが正しい。→正解。

設問(r)以降は、新たな制約が加わる。各株に買える上限数が設定されている。

会社 株価(1991) 株価(2011) 上限
Dale 12 39 3
JCN 10 13 無限
Macroware 18 47 2
Pear 15 45 1

(r): 30ドルもっていた場合の最適な買い方は？

設問(b)でやったのと同じことを考える。Pearは2つも買えないので、DaleとPearを一つずつ買えば良い。→正解。

(s): 120ドルもっていた場合の最適な買い方は？

無限に買えるJCNは利益率が一番低いので、まず他の株を買えるだけ買って、余ったお金でJCNを買うのが良い。

  • Dale3株: 36ドル
  • Macroware2株: 36ドル
  • Pear1株: 15ドル

合計して、87ドル。余ったお金は120-87=33ドル。このお金でJCNを3つ買う。→正解。

(t): 買える株の数に制約がある場合のアルゴリズムの擬似コードを書け。時間計算量も記せ。justificationも記せ。入出力は以下である。

入力

  • total: 持っているお金

  • count: 株の種類数

  • start: 1991年時点での株価の配列

  • end: 2011年時点での株価の配列
  • limit: 株ごとの買える株数の配列

出力

  • 儲けの最大値

stock-table-Aの擬似コードにおいて、profitにあたる配列だけ計算すれば良いので、(purchase配列は必要ない)擬似コードをなるべく真似する。 limit配列を作って、株を買うたびにlimit配列の数値をデクリメントし、if文で買えるかどうか判断すればよいのでは。 limit配列はdpの配列に載せることで、各状態(cashとstock)に対する残り株数がわかるようにする。

create table profit
for cash=0 to total
  profit[cash, total] = (cash, limit)
  for stock = 1 to count
    profit[cash, stock] = profit[cash, stock-1]
    current_limit = profit[cash, stock][1]
    if start[stock] <= cash and current_limit[stock]:
      leftover = cash - start[stock]
      current = end[stock] + profit[leftover, stock][0]
      if profit[cash, stock][0] < current:
        current_limit[stock] -= 1
        profit[cash, stock] = (current, current_limit)

justificationとしては、上に述べた漸化式

limitに関する部分はO(1)で計算できるので、時間計算量は、O(total*count)

解答は、漸化式を簡単にしない形で各株を0, 1, ..., k個買うことをそれぞれ調べている。よって解答のアルゴリズムの計算量は[tex:O(totalcountcount)]である。 上に書いたアルゴリズムの場合、k回調べることをしなくて良いので、こっちのが早いと思うが、確かめる術がない。 あと、解答を読んでいて思ったが、自分のアルゴリズムはlimit配列をまるごとdp配列に埋めているが、該当する株の残量だけ、つまりlimit[stock]だけ渡していけば良い。 注目している株を買う数量を選ぶときに、他の株の残量は関係ないので。

以上、Problem Setを解き終わった。 講義の課題としてナメてかかっていて、たくさん間違えることも多くて難しかった。 MITの講義のレベルはさすがに高いという感じ。 まだざっと一周しただけなので、解き直しをしっかりやりたい。（解き直ししたら過去の記事にも追記します）