今日はナップサック問題の関連解法について続けます。主な内容は、動的計画法です。
この解法について考えたのは、前の数日間のソフトウェア設計師の試験のアフタヌーンセッションのアルゴリズムの問題を思い出したからです。私は参加者で、内容はおおよそ次のようなものでした：通常、各種の食品には異なる栄養価がありますが、顧客は最小のコストで最大の栄養価を得るアルゴリズムを実現することがよくあります（食品は重複しない）。現在、N ドルを使って最大の栄養価を得ることが求められています。
分析：解法の原理はおそらく言わなくてもわかると思いますが、ナップサック問題です。ソフトウェア設計師の試験では、動的計画法が使用されています。今日のトピックに関連しているので、以下のコードを見てみましょう。
この問題の動的計画法の原理：顧客が異なる食品を選択すると、異なる栄養結果が生じるため、価格と栄養価の合計との関係を動的に結びつける必要があります。関連配列を作成し、それによって各価格の費用が異なる結果を生み出すことができます。その後、大小の選択を行い、既存の選択の前提条件の下で一定の価格の食品を追加します。追加後の合計が超過する場合は除外し、または追加した食品の栄養価値がより安価な食品の栄養価値よりも小さい場合も除外します。これにより、各価格帯の食品の最大栄養価値を求めることができます。その後、要件に応じて特定の価格帯の結果を出力します。
以下の解の配列に関しては、得られた結果が特定の価格帯の最大栄養価値であるため、このリストに含まれる食品を順番に求める必要があります。そのため、f [i][S] == f [i+1][S] の間で比較を行い、同じ場合は栄養価値が変わらず、追加しないことを意味します。そうでなければ、食品 i が追加されたことを意味します。結果を出力します。
/*
* ナップサック問題の動的計画法による栄養パック問題の解法
* 著者：cg
* 日付：2008 年 12 月 26 日
/
#include "stdio.h"
#define N 6 /* 食品の数を定義 */
#define S 100 /* 最大の栄養サイズ */
int main() {
int p [N] = {100,22,80,25,10};/* テストデータの価格を表す */
int w [N] = {50,30,51,12,5};/* テストデータの栄養を表す */
int f [N + 1][ N + 1];/* 動的価格栄養関係の配列 */
int result = 0;/* 求められる結果 */
int x [N] = {0};/* 解の配列を定義 */
int i,j;/* カウンタを定義 */
int temp;
for (j = 0; j < S+1; j++)
f [N][j] = 0;/* 初期化 */
for (j = w[N]; j <= S; j++)
f [N][j] = p [N];/* 価格の初期化 */
for(i = N-1; i > 1; i--) {
for(j = 0; j < S+1; j++)
f[i][j] = f[i+1][j];
for(j = w[i]; j <= S; j++){
f[i][j] =
f[i+1][j] > f[i+1][j-w[i]] + p[i] ?
f [i+1][j] : f [i+1][j-w [i]] + p [i];/* 最大値かどうかを判断し、それ以外は保持する */
}/*for*/
}/*for*/
f[1][S] = f[2][S];
if (S >= w[1])
f[1][S] =
f[1][S] > f[2][S-w[1]] + p[1] ?
f [1][S] : f [2][S-w [1]] + p [1];/* 最終結果の処理 */
temp= f[1][S];
for (i = 1; i < N; i++){/* 解の配列 */
if (f[i][S] == f[i+1][S])
x[i] = 0;
else {
x[i] = 1;
temp-= w [i];/* 追加された栄養を減らす */
}/*else*/
}/*for*/
x[N] = f[N][S] ? 1 : 0;
result = f[1][S];
printf ("最適な結果は % dn", result);/* 最大の結果を出力 */
for (i = 1; i <= N ; i++) {/* 個別に結果を出力 */
if (x[i] == 1) {
printf ("価格： % d", p [i]);
printf ("栄養： % dn", w [i]);
}/*if*/
}/*for*/
system("pause");
return 0;
}