アルゴリズムの勉強(ナップサック問題と動的計画法)

2019.5.29

会社の同僚とアルゴリズムの勉強会を少人数で始めました。最終的にはGoogleに転職する頭でアルゴリズムを考える力をつけるのが目的です。実際にやってみて一人で勉強していくよりも相談しながら解いていくほうが考えがより深まるような感じがあります。

今回はナップサック問題を動的計画法で解くのを勉強しました。数年前に応用情報を受験したときの本番で出た問題でした。当時はナップサック問題を知らなかったので、なんとなく解いた記憶があります。

ナップサック問題

容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか

要は、効率よくナップサックに詰め込むために品物の組み合わせを求めよってことです。

実際に出た問題

実際に出た問題はこちらです。(応用情報技術者過去問題 平成29年秋期 午後問3)

問題文が結構長いですが、要約すると下記のようなitemsの配列とcontainerSizeが渡されて、valueの最大値とその時のitemsの組み合わせを返す関数をつくるという感じです。

const items = [
  { size: 1, value: 2 },
  { size: 2, value: 6 },
  { size: 3, value: 9 }
];

const containerSize = 4;

サンプルを作りました。

https://codepen.io/kwst/pen/wbrRMR?editors=1011

作成した関数はこれです。ほぼ解答のままです。

function getMaxValue(containerSize, items) {
  const maxValue = new Array(containerSize + 1).fill(0);
  const choice = [];
  
  for (let s = 0; s < items.length; s++) {
    for (let t = items[s].size; t <= containerSize; t++) {
      const temp = maxValue[t - items[s].size] + items[s].value;
      if (temp > maxValue[t]) {
        maxValue[t] = temp;
        choice[t] = s;
      }
    }
  }
  let k = containerSize;
  const res = new Array(items.length).fill(0);
  while(choice[k] >= 0) {
    res[choice[k]]++;
    k = k - items[choice[k]].size;
  }
  return {
    maxValue: maxValue[containerSize],
    choice: res
  };
}

動的計画法

実際に組み合わせを求めようとすれば総当たりで計算していくので、O(N^N)になるかな？

動的計画法を用いているので、一度それまでの結果をキャッシュしておいて、計算を削減しています。その結果O(items.length * N)になります。

試験の会場で実際に解いているときは、答えを出すことに必死でしたので結果をキャッシュして計算を削減してるんだなぁとか噛みしめる余裕もなかったです。もう一度考え直してみるとなるほどなぁという感じです。

© 2019-2024 kwst.site.