きっかけ
とあるプロコンに参加した時に、ナップサック問題の類似問題に出会ったので、
ググったところ、最適値を求めるプログラムを見つけることはできても、
最適解を求めるプログラムを見つけることができず、
結局自分で調べてコーディングするというある意味タイムロスをくらったので、
少しでも他の人の助けになれば。
ナップサック問題
「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）
が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、
ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。
要はナップサックの耐荷重を超えないギリギリまで物を詰めたときの
総価値を最大にしたいってことです。
今回は同じものは入れることのできない0-1ナップサック問題を扱います。
最適解へのアプローチ
今回使う金塊は次の通り。これを先頭から5個までの金塊を使って重さ4を超えないように詰めたときの最大価値を計算、その時の金塊の組み合わせを求めたい。
| 重さ | 価値 |
|---|---|
| 2 | 3 |
| 1 | 2 |
| 3 | 6 |
| 2 | 1 |
| 1 | 3 |
| 5 | 85 |
最適値はDPを用いてテーブルを作成することで求めることができる。
漸化式は以下の通り。例えば「先頭から5個までの金塊を使って重さ4を超えないように詰めたときの最大価値」を知りたいときはdp[5][4]にアクセスすることでわかる。
(この答えは3つ目と5つ目の金塊を使えば最大価値9を得られる。)
上の式より、最適解を得るためには、dp[i+1][w]にmax関数の第一引数の値が入ればその時のi番目の金塊をナップサックに入れることは確定するので、以下のようなコードで求めることができる。
// Solving knapsack problem with DP
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
// input
// n = value of gilt
// W = limit of total weight
// weight[] = weight of each gilt
// value[] = value of each gilt
const int n=6, W=8;
const int weight[]={2,1,3,2,1,5}, value[]={3,2,6,1,3,85};
// DP table
int dp[10][10];
//------------------------------------------------------------------------------
/// 指定されたDPテーブルの要素はどの金塊の組み合わせで作れるのかを逆算する
/// @param i 使って良い金塊の個数 i番目までの金塊を使える
/// w ナップサックの耐荷重
/// ans 答え,金塊を0:入れない 1:入れる
void DP_OptimalSolution(const int i, const int w,int ans[n]){
int local_w=w;
for(int local_i=i-1;local_i>=0;local_i--){
if (local_w >= weight[local_i] && max(dp[local_i][local_w-weight[local_i]] + value[local_i], dp[local_i][local_w])==dp[local_i][local_w]){
ans[local_i]=0;
}
else if(local_w >= weight[local_i] && max(dp[local_i][local_w-weight[local_i]] + value[local_i], dp[local_i][local_w])==dp[local_i][local_w-weight[local_i]] + value[local_i]){
ans[local_i]=1;
local_w=local_w-weight[local_i];
}
else if(local_w < weight[local_i]){
ans[local_i]=0;
}
}
}
int main() {
// init
for (int w = 0; w <= W; ++w) dp[0][w] = 0;
// DP table
for (int i = 0; i < n; ++i) {
for (int w = 0; w <= W; ++w) {
if (w >= weight[i]) dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
else dp[i+1][w] = dp[i][w];
}
}
//answer
int ans[n];
DP_OptimalSolution(5,4,ans);
for(int i=0;i<n;i++){
cout << ans[i] << endl;
}
return 0;
}
実行結果は以下の通り。金塊を0は入れない。1は入れることを示している。
よって今回は3番目と5番目の金塊をナップサックに入れることで最大値を得られることが解る。
0
0
1
0
1
0