01リュックサック問題の分析と最適化

リュックサックの問題はダイナミック企画の経典問題で、複数のサブ構造に分けることができます.
1番目のものだけを使用してリュックサックの容量が1の場合、リュックサックの最大値はV[1][1]です.
1番目のものだけを使ってリュックサックの容量が2の場合に入れる最大の価値はV[1][2]です.
1番目のものだけを使用して、リュックサックの容量がjの場合、リュックサックの最大値はV[1][j]です.
1,2番目のものだけを使用して、リュックサックの容量がjの場合、最大値はV[2][j]です.
第1、2、3…i個だけを使用して、リュックサックの容量がjの場合、リュックサックの最大値はV[i][j]です.
第1,2,3,i-1個を使用すると、荷物の残り容量がjの場合、i番目のものを選ぶ時、i番目の荷物の重さがリュックサックの容量より大きい場合、i番目のものは入れられません. V[i][j]=V[i-1][j]
そうでなければ、中に入れるか入れないかを選ぶことができます.どれが一番大きいかを見るべきです. 
コードは以下の通りです

#define M 8 //    
#define N 6	//     
#define max(x,y) x > y ? x : y	//       
int V[N + 1][M + 1] = {0};	//                     ，  V[0][] V[][0]      0    0        ，          
int weight[N+1] ={0,1,2,3,4,5,6};	//  weight[] value[] 0        0，    ，       ，      
int value[N+1] = {0,2,3,4,5,6,7};
void package01()
{
	for(int i = 1; i <= N; i++)		//i   i   ，i      ，      ，         。  V[i][]      V[i-1][]   ，                     
	{
		for(int j = 1; j <= M; j++)	//j            j
		{
			if(j >= weight[i])	
			{
				V[i][j] = max(V[i - 1][j], V[i - 1][j - weight[i]] + value[i]);
			}
			else
			{
				V[i][j] = V[i - 1][j];
			}
		}
	}
}

実は配列は前の行のデータに基づいて書き込みます.二次元配列ではなく、一次元配列で、自分自身で更新すればいいです.ポイントは「i-1」「j-weight[i]」というデータです.表の中の行にjより小さいデータを探したいという意味です.一次元に換えれば、私が探しているのは自分自身です.(一行のみ、前の行がない)j左側のデータは、前回(i-1)に書き込まれたものであることを保証しなければなりません.必ず左から右にデータを書き込むことができません.そうすれば、[i-1]j-weight[i]に対応するのは、今回(i)に書き込まれたもので、前回のデータが利用されていないので、jサイクルはMから1まで、右から1次元の配列にデータを書き込むべきです.
コードは以下の通りです

void package01EX()
{
	for(int i = 1; i <= N; i++)
	{
		for (int j = M; j >= 1; j--)
		{
			if (j >= weight[i])
			{
				V[j] = max(V[j], V[j - weight[i]] + value[i]);
			}
		}
	}
}

最初は頭が痛くて、第iのものを選んで、置くか入れないかのどちらかを選ぶ時に、なんとなく置いたほうがいいと思います.前の選択肢が決まっていると思いますが、間違っています.前の選択肢は決まっていません.直接に表に記入してもいいです.その二次元配列によって表を記入します.まず0に初期化して、書いたら、実際にi番目のものが選ばれました.商品の場合、前の各項目の選択はまったく確定されていません.二次元配列はすでに前の方から選択可能な可能性を示しています.例えば、試し的な選択をして、i番目のものを置くといいです.jはweight[i]を引いて、iはマイナス1を引いて、前の行のデータを見てみます.実は左寄りの方に対応するあのVはいくらですか?これを置くことに対する価値です.置かないと、そのままその頭のVに等しいです.つまりV[i-1][j]です.置かないということです.私の最後のステップはV[i-1][j]からです.移行してきたのは、上から左に行くという段階から移行してきました.そして前の二つの道は彼らの前から移行してきました.一歩ずつ表に記入してもらったので、対応していない前の選択とは違って、道を下りてきたのではなく、容量が減って、上の行にデータを探して左に探します.容量は右より小さいです.つまり、前の行の左のデータは右のデータより小さいかもしれません.右のデータより大きいはずはないです.この小さい点のデータにi番目のものの価値が頭のデータより大きいということは、入れる価値が大きいということです.反対に、つまり今の段階でi番目のものを置くかどうかは前のステップの容量を決めます.いくら積んでいますか?とにかく容積の多少は全部並べられました.自分で探したらいいです.前の情報はまた参考にしてくれました.置くか入れないかを分析できます.