C言語、動的計画法の動きを教えてほしい

Question

基本情報技術者試験対策として、今C言語の動的計画法を勉強しています。
そこでどうしても分からない壁にぶち当たりました。
ナップザック問題なのですが、重さ１価値２のAと、重さ２価値６のBを、任意の重さVに収まるように選択し最も価値を高くさせるというものです。おそらく、最もスタンダードな形のナップザック問題です。
この問題のプログラムが

#include <stdio.h>
int main(void)
{
int N = 2;
int size[2] = {1, 2};
int value[2] = {2, 6};

int V;
printf("ナップザックの容量制限入力");
scanf("%d", &V);
int maxvalue[V];
int choice[V];

for(int k = 0; k <= V; k++){
maxvalue[k] = 0;
choice[k] = -1;
}

/*動的計画法のメイン。分からない部分*/
for(int s = 0; s <= N-1; s++){
for(int t = size[s]; t <= V; t++){
int temp = maxvalue[t-size[s]] + value[s];
if(temp > maxvalue[t]){
maxvalue[t] = temp;
choice[t] = s;
}
}
}

int k = V;
while(choice[k] >= 0){
printf("choice[k] = %d\n", choice[k]);
k = k - size[choice[k]];
}

printf("価値合計 = %d\n", maxvalue[V]);
return 0;
}

です。
コードにコメントしているように、動的計画法のメインとなる部分の意味が分かりません。
どうしてこれでうまく動くのでしょうか。
最初のfor文（s=0の方）があれば常にAか常にBを入れるという動作になってしまう気がするのですが、どうしてならないのでしょうか。
よろしければs=1のときtmpがこの値になって…など具体的な説明も交えて頂けるとありがたいです。

よろしくお願いいたします。

Answer 1

最初のfor文（s=0の方）があれば常にAか常にBを入れるという動作になってしまう気がするのですが、どうしてならないのでしょうか。

最初に「Aばかりを入れた状態」で仮のmaxvalueを作っていきます。次に、Bに入れ替えてより多く詰められるようになるならmaxvalueを「Bも入れたものに更新していく」という流れです。

Comments

[Satsumaimo]

回答ありがとうございます！
maxvalueにAばかり入れた後、
int temp = maxvalue[t-size[s]] + value[s];
でBを入れて
if(temp > maxvalue[t]){
maxvalue[t] = temp;
でBを入れた方が大きければそっちを採用、ということでいいでしょうか？
maxvalue[t-size[s]]
になっているのは、tのときに入っているAをどけて、代わりにBを入れている動作ということであっていますでしょうか？
返信いただければ幸いです