01リュックの状態遷移方程式

こんな問題は普通だが、忘れてしまった.特に状態遷移方程式は、どのように導いたのか覚えていないので、ここで振り返りましょう.else F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+v[i]); ここでのF[i-1][j-w[i]]は、現在の荷重jがw[i]を除いた最大収益を表し、v[i]を加えると現在のF[i][j]のもう一つの収益であり、この収益をF[i-1][j]と比較して最大収益を得る.例を挙げます.

#include
using namespace std;

int main()
{
    int nArr[6][13] = {{0}};
    int nCost[6] = {0 , 2 , 5 , 3 , 10 , 4};  //  
    int nVol[6]   = {0 , 1 , 3 , 2 , 6 , 2}; //    
    int bagV = 12;

    for( int i = 1; i< sizeof(nCost)/sizeof(int); i++)
    {
        for( int j = 1; j<=bagV; j++)
        {
            if(j1][j];
            else
                nArr[i][j] = max(nArr[i-1][j] , nArr[i-1][j-nVol[i]] + nCost[i]);       
            cout<' ';
        }   
        cout<cout<5][12]<return 0;
}

コードは私が探している他の人のものです.私は書くのがおっくうなので、コードの原文を貼ります.http://blog.csdn.net/FX677588/article/details/68951593最後にこの大物の一言を写した.
ダイナミックプランニング(Dynamic Programming,DP)と分治の違いは,分割されたサブ問題が重複していることであり,解の過程で重複した部分について一度解くだけで結果を記録し,他のサブ問題を直接使用すればよいため,繰返し計算過程を減らすことである.
動的計画解は以下の性質を有する:最適サブ構造特性、サブ問題重畳特性最適サブ構造特性:最適解はそのサブ問題の最適解を含み、すべてのサブ問題の解を統合するのではなく、最適な解線路を探し、部分子最適解を選択して最終的な最適解に達する.サブ問題オーバーラップの性質:サブ問題の解を先に計算し,サブ問題の解から問題の解を構築する(サブ問題がオーバーラップしているため,サブ問題の解を次のステップとして記録して用いることで,直接メモから読み取ることができる).メモに初期状態を先に記録します.