デジタルダイナミックプランニング小例のmatlabプログラム実現-リュックサック問題

目次

1、問題説明

2、分析構想

符号説明

プロセス分析

コードステップ

3、matlab実現

4、プログラム結果

1、問題の説明
番号がそれぞれa,b,c,d,eの5種類の金銀の物品があって、それらの重量はそれぞれ2,2,6,5,4で、それらの価値はそれぞれ6,3,5,4,6で、既存の1つの荷重が10のリュックサックがあって、どのようにリュックサックに金銀の物品の価値の総和を持って最大になりますか?
2、考え方を分析する
シンボルの説明
x(k):第k段階における状態を示し、状態が第k段階におけるリュックの重量u(k):第k段階における意思決定を示し、意思決定1は第kの物品をリュックに入れることを示し、0は逆である.v(x(k),u(k):第k段階における段階指標,すなわち決定的に取り出された第kの物品の価値f(x(k):総目標関数,すなわちリュックサック荷重の範囲内で最大の価値を持つ金銀財宝を表す
プロセス分析
5種類の金銀物品がa,b,c,d,eの順序で排出されると仮定すると,金銀物品の順序をシステムの段階とすることができる.すなわち、第1の物品(a)を第1の段階、第2の物品(b)を第2の段階、第3の物品(c)を第3の段階、…とすると、この問題は5つの段階に分けられる.そのシステムの状態x(k)がリュックの現在の重量であると、状態遷移経路はx(k+1)=x(k)+u(k)、段階指標はv(x(k)、u(k)=x(k)となる.
総目標関数f(x(k))は、k段目の状態x(k)からプロセス終了までのリュックサックに装着される金銀の総価値が最も大きく、すなわちf(x(k)=max(v(x(k),u(k))+f(x(k+1))である.
分析がはっきりしないと思ったら、この文章を参考にしてください.https://blog.csdn.net/mu399/article/details/7722810
コードステップ
以上の解析を理解すると,次はコードの実装である.コードは上記の分析に基づいて記述され,システムには5つの段階があり,各段階の決定は0,1で表される.
コードの第1ステップ:aマトリクスの第1行で1,2,3,4,5システムの段階を格納し、第2行は金銀重量を格納し、第3行は金銀価値を格納する.
コード第2ステップ:全ての場合のシステム状態(以下、上位6行のみ)を生成する1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0例えば、上から出力されたデータマトリクス種の第1行第1列が1であることを示す第1段階の決定値が1である(つまりこの5つの順序で並べられたものは、1つ目のものをリュックに入れたもの)で、1行2列目が1で、2段階目の決定値が1であることを示す(2番目のものをリュックに入れる)と、後ろの数字は同じです.2行目の数字もそうですが、違う場合を示しているだけです.そのため、1行目はすべてのものをリュックに入れることを示していますが、リュックの荷重を超えていることが明らかになりました.そのため、裏面のコードにはリュックの荷重の制約が必要です.
コード第3ステップ:リュックサックの荷重に制約条件を記入する.すなわち、リュックサックの荷重条件を満たす様々な状況のみを計算し、値をfに格納するf=(a(3,:)*v(i,:)’)
コード第4ステップ:リュックサックが装着した総価値を算出して出力し、最終的にリュックサックが装着できる価値は最大15である.(詳細はコードを参照)
3、matlab実現

clear,clc
a = [1 2 3 4 5;     %         ，         
     2 2 6 5 4;     %         
     6 3 5 4 6];    %         

b = perms(a(1, :));
v = [];
for i = 1:size(a,2)-1
    c = b;
    id1 = find(c <= i);
    id2 = find(c >  i);
    c(id1) = 0;
    c(id2) = 1;
    c = unique(c,'rows');
    v = [v; c];    				%  0、1     k     
end
v = [ones(1,5); v; zeros(1,5)]; %              v 
 
F = [];
for i = 1:size(v,1)
    if (a(2,:) * v(i,:)') <= 10 %     （        ）
        f = (a(3,:) * v(i,:)'); %     
        F = [F, f];             %     
    end
end
best_value = max(F)             %        

4、プログラム結果

best_value = 15