C++でナップサック問題をDP法で解いてみた

はじめに

「数理最適化問題を解きたいなー」と思い，昨日は最急降下法を解いたのですが，まだ解きたかったのでナップサック問題をDP(Dynamic Programming)法を使って解いてみました．

ナップサック問題とは

端的に言うと、

「２つの定数（満足感/値段 etc.）を持つ商品がいくつかあり，使える金額の中で満足感を最大にする問題．」

である．

DP法

動的計画法の事．細かい説明はできないので，他のページをみて欲しい．一言で言うと，

「表を作ってそれまでの選択肢から最大値を求め，それを更新していき，最後に結果が出る．そのとき，常に条件（上限金額）を満たすようにする．」

である．

問題

果物(fruits)という配列があり，各果物の(名前，満足度，値段）がわかっているものとする．ここでの値は自分で決めたものなので，深い意味はない．

それぞれの果物の在庫は１つとし，使える金額は１０円とする．

このときの最大の満足度を求める．

プログラム

解くために，sackという２次元配列を準備し，果物を順に(買う/買わない)場合について満足度と金額を追加していった．便宜上，sack[0]には空の配列を，格納した.

KnapsackProblem.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;

constexpr int MAX_MONEY = 10;

vector<tuple<string, int, int>> fr{
  // tuple ("fruit_name", satisfaction, value)
  make_tuple("", 0, 0),
  make_tuple("Apple", 5, 4),
  make_tuple("Amelanchier", 3, 3),
  make_tuple("Shipova", 2, 2),
  make_tuple("Melon", 8, 4),
  make_tuple("Cherry", 1, 1),
};

void view(const vector<vector<int>>& vv){
  for(const auto& v : vv){
    for(const auto& e : v){
      cout << setw(3) << e << " ";
    }
    cout << endl;
  }
}

int main(){
  vector<vector<int>> sack(fr.size(), vector<int>(MAX_MONEY+1));
  for(size_t i=1; i<sack.size(); ++i){
    for(size_t j=0; j<sack[i].size(); ++j) sack[i][j] = sack[i-1][j];
    sack[i][get<2>(fr[i])] = max(sack[i][get<2>(fr[i])], get<1>(fr[i]));
    for(size_t j=0; j<sack[i].size(); ++j){
      if(sack[i-1][j]!=0){
        if(j+get<2>(fr[i])<sack[i].size()){
          sack[i][j+get<2>(fr[i])] = max(sack[i][j+get<2>(fr[i])], sack[i-1][j]+get<1>(fr[i]));
        }
      }
    }
  }
  view(sack);
  return 0;
}

これを実行した場合，以下となった．これは，更新していった結果の表である．

output

  0   0   0   0   0   0   0   0   0   0   0 
  0   0   0   0   5   0   0   0   0   0   0 
  0   0   0   3   5   0   0   8   0   0   0 
  0   0   2   3   5   5   7   8   0  10   0 
  0   0   2   3   8   5  10  11  13  13  15 
  0   1   2   3   8   9  10  11  13  14  15 

となり，最大の満足度は15となった．

おわりに

なんとか解けました．
少し無駄がありそうなので，気が向いた時に更新します．（tupleを使わない方がいいかも）
stringを結合するなどして，選んだ果物を確認できるようにしようかなとは思っています．