リュックサック-01リュックサック

01リュックサックを知るときは、01リュックサックの質問方法の違いに注意してください.
初期化は2つのケースに分かれています
(1)、バックパックの要求がちょうど満たされている場合はf[0]=0,f[1~w]=-INFを初期化する.  
(2)、必要でなければちょうどf[0~v]=0を満たす.
 
 
 
タイトル
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
    
全体的な考え方:
リュックサックの問題はずっと自分を困らせているので、今日からリュックサックの問題の整理に着手して、第1種-01リュックサックは最も簡単な規則の問題だけではなくて、更に最も簡単なリュックサックの問題で、しかしやはり1つの始まりです
リュックサックの問題は実は体積を遍歴対象として、すべての品物の体積を遍歴して、V-の同時に盛ることができるかどうかを見て、もしできるならば、残りの体積が盛ることができる最大値を現在の体積に加えて記録した価値に加えて、循環して、最後に直接Vを出力することができる価値が最も良い解であることを知っています.
本アルゴリズムを理解するにあたっては、直接単純に考えるのは難しいが、本人から見れば実例を挙げて、シミュレーションアルゴリズムの過程で本アルゴリズムを理解し、その大まかさを理解してからその真髄を理解する必要がある.
 
 
解法1:
状態方程式:f[v]=max{f[v],f[v-c[i]+w[i]}
単純な1次元配列

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int main()
{
    int T,N,V;//T        N       V         
    int f[1001],vol[1001],val[1001] ,tem;//f  i                vol[i]  i        val[i]   i      
    scanf("%d",&T);


    while(T--)
    {
        int i,j;
        scanf("%d %d",&N,&V);
        for(i = 0 ; i < N ; i++)
        scanf("%d%d",&vol[i],&val[i]);
        memset(f,0,sizeof(f));
        for(i = 0 ; i < N ; i++)  //  i   
        {
            for(j = V ; j >= vol[i]; j--)
            {
                tem = f[  j-vol[i]  ] + val[i];
                if( f[j] < tem )
                f[j] = tem;
            }
        }
        cout<<f[V]<<endl;
    }
    return 0;
}

 
解法二
2 D配列を使用して、、、が完了していません.