スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ナップサック問題を動的計画法で解くCプログラムの例

ナップサック問題を動的計画法で解く C プログラムの例。

ナップサック問題とは、正の整数の列 v[0], v[1], ..., v[n-1] と w[0], w[1], ..., w[n-1]、および正の整数 W が与えられたとき、Σw[i] (i∈S) が W 以下という条件の下で Σv[i] (i∈S) が最大になる集合 S ⊆ { 0, 1, ..., n-1 } を求める問題です。

動的計画法は、最適化問題を解くためのボトムアップ的な手法です。与えられた問題を解く際、より小さいサイズの問題から順に解き、前段階の解を利用して次段階の解を求め、最終的にもとの問題の解を得ます。プログラムの動作においては、ある時点までの計算結果をメモリに記憶しておき、それを次の計算で再利用することにより、余分な計算を省いて効率化を図ります。

プログラム例

#include <stdio.h>
#include <string.h>

#define IMAX 100
#define JMAX 100

int dp[IMAX+1][JMAX+1];  /* 動的計画法で用いる */
char isPacked[IMAX];  /* 品物を詰めたかどうか */

int knapsack(
  const int v[],   /* 価値 */
  const int w[],   /* 重さ */
  int numOfItems,  /* 品物の個数 */
  int wUpperBound  /* 総重量の上限 */
)
{
  int i, j;

  /* dp[0][j] = 0 (j=0,...,wUpperBound) */
  memset( dp[0], 0, sizeof(int) * (wUpperBound + 1) );
  /* isPacked[i] = 0 (i=0,...,numOfItems-1) */
  memset( isPacked, 0, numOfItems );

  /* 価値の総和の最大値を動的計画法で求める */
  for ( i = 0; i < numOfItems; i++ ) {
    for ( j = 0; j <= wUpperBound; j++ ) {
      if ( w[i] <= j && dp[i][j] < dp[i][j-w[i]] + v[i] ) {
        dp[i+1][j] = dp[i][j-w[i]] + v[i];
      }
      else {
        dp[i+1][j] = dp[i][j];
      }
    }
  }

  /* 詰めた品物を調べる */
  j = wUpperBound;
  for ( i = numOfItems - 1; i >= 0; i-- ) {
    if ( w[i] <= j && dp[i][j] < dp[i][j-w[i]] + v[i] ) {
      isPacked[i] = 1; 
      j -= w[i];
    }
  }

  return dp[numOfItems][wUpperBound];
}

int main(void) 
{
  const int v[] = { 5, 2, 9, 7, 3 };
  const int w[] = { 4, 1, 7, 5, 2 };
  int numOfItems  = 5;
  int wUpperBound = 10;
  int sol, i;

  sol = knapsack( v, w, numOfItems, wUpperBound );
  printf( "solution: %d\n", sol );
  printf( "id  v  w\n" );
  for ( i = 0; i < numOfItems; i++ ) {
    if ( isPacked[i] ) {
      printf( "%2d %2d %2d\n", i, v[i], w[i] );  
    }
  }

  return 0;
}

実行結果:

solution: 14
id  v  w
 0  5  4
 1  2  1
 3  7  5

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。