[セットトップ]ダイナミックプランニング0-1リュックサックの問題解決

著作権所有、転載は出典を明記してください!
動的計画は空間で時間を変える方法の抽象である.その鍵は,サブ問題の発見とその結果の記録である.そして,これらの結果を用いて演算量を軽減する.例えば01リュックの問題です.
/*一人の旅行者はMキロまで使えるリュックサックを持っていて、今はN個の品物があって、それらの重さはそれぞれW 1、W 2、...、Wn、それらの価値はそれぞれP 1,P 2,...、Pn. もしすべての品物が1つだけ旅行者に最大の総価値を得ることができるならば.入力形式:M,N W 1,P 1 W 2,P 2…出力形式:X*/
リュックの最大容量Mが不明なためです.だから、私たちのプログラムは1からMまで一つ一つ試します.例えば、Nアイテムの1つを選択し始めます.M対応のリュックサックを見て、入れられるかどうか、入れられるかどうか、そしてたくさんのスペースがあれば、多くのスペースにN-1アイテムの中で最大の価値を入れることができます.どのようにして総選択が最大の価値であることを保証することができますか?時計を見てください.テストデータ:10,3,3,4,5,6
c[i][j]配列は1,2,3号品を順次選択した最大の価値を保存する.
この最大の価値はどうやって得たのでしょうか.リュックサックの容量が0から、1番の品物は先に試して、0,1,2,の容量はすべて置くことができません.だから0を置いて、リュックサックの容量は3で中に4を入れます.このように、このリュックサックの容量は4,5,6,....10の時、最善の案はすべて4を置くことです.もし1番の品物をリュックサックに入れたら.2番の品物を見ます.リュックサックの容量が3の場合、最適な案は前の列の最価格案cが4である.リュックの容量が5の場合は、自分の重さ5がベストです.リュックサックの容量が7の場合、明らかに5に1つの値が加算されています.誰を追加しますか?明らかに7-4=3の時です.前の列のc 3の最適な案は4です.だから.全体的な最適案は5+4が9である.そうですか.ずらりと押し下げる.一番右下に置かれたデータが最大の価値です.(注意3列目のリュックの容量が7の場合、ベストプランは自分の6ではなく前の列の9.説明このとき3番のものは選ばれなかった.1,2番のものを選んだ.だから9.
以上の最大価値の構造過程から見ることができる.
f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}これが本に書いた動的計画方程式である.今度は分かりましたか.
以下は簡単なプログラムコードです(このコードは理解しやすいように最適化されていませんので、ご了承ください):

//
//  main.cpp
//  TestC++06
//
//  Created by fei dou on 12-8-11.
//  Copyright (c) 2012  vrlab. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#define N 3
using namespace std;
const int W[] = {3, 4, 5};
const int P[] = {4, 5, 6};
void zeroOnePake(const int objNum, const int volumOfPack, const int* W, const int* P, vector<int> &result, int &maxValue);

void zeroOnePake(const int objNum, const int volumOfPack, const int* W, const int* P, vector<int> &result, int &maxValue)
{
    int **c = new int*[objNum + 1];//        ，      ，                         ，    
    for (int i =0; i <= objNum; ++ i)
        c[i] = new int[volumOfPack + 1];
    
    bool **d = new bool*[objNum + 1];    //           
    for (int i = 0; i <= objNum; ++ i)
    {
        d[i] = new bool[volumOfPack + 1];
        memset((void*)d[i], false,sizeof(d[i])); //    0
    }
    
    //   c
    for(int i =0; i <= volumOfPack; ++i)
        c[0][i] = 0;//            
    
    //      
    for (int i =1; i <= objNum; ++i)
    {
        for (int j =0; j <= volumOfPack; ++j)
        {
            int tempC = 0;
            if (j - W[i] >= 0)
            {
                tempC = c[i - 1][j - W[i]] + P[i - 1];
                d[i][j] = true;//     i  
            }
            c[i][j] = max(c[i-1][j], tempC);
            
        }

    }
    
    //      
    maxValue = c[objNum][volumOfPack];
    
    //         
    int i = objNum;
    int j = volumOfPack;
    while (i >= 1)
    {
        if (d[i][j] == true)
        {
            result.push_back(i);
            -- i;
            j -= W[i];
        }
        else
            -- i;
    }
    reverse(result.begin(), result.end());//  ,            
    //    
    for (int i =0; i <= objNum; ++i)
        delete[] c[i];
    delete[] c;
    for (int i =0; i <= objNum; ++ i)
        delete[] d[i];
    delete[] d;
}


int main (int argc, const char * argv[])
{

    vector<int> result;
    int maxValue;
    zeroOnePake(N, 10, W, P, result, maxValue);
    cout << "      ：" << maxValue << endl;
    cout << "      ：" << endl;
    for (int i =0; i < result.size(); ++ i )
        cout << result[i] << "  ";
    cout <<endl;
    return 0;
}

プログラムの実行結果は次のとおりです.
計算結果は:11
入選したものは次のとおりです.
2  3