ダイクストラのようなものが必要な場合は、ダイクストラをやってみませんか？グラフの解釈でいくつか変更する必要がありますが、それは非常に実行可能のようです。
ダイクストラは、最小コスト基準に従ってノードを決済します。その基準を「会社が失ったお金」に設定します。また、ダイクストラでノードを決済し、ノードが正確に何になるかを決定する必要があります。ノードを時間とプロパティの状態と見なします。たとえば、x年前のマシンが稼働している4年目です。0年目には、失われるお金は0になり、マシンはなくなります。次に、可能なすべてのエッジ/選択/状態遷移を追加します。ここでは「マシンを購入する」です。最終的に、ダイクストラPQ [1年目、1歳の稼働中のマシン]に一定のコストで新しいノードができあがります。
そこから、いつでもマシンを販売する（[1年目、マシンなし]ノードを生成する）、新しいマシンを購入する[1年目、新しいマシン]）、または同じものを続行する（[2年目、2歳のマシン]）ことができます。 。5年目（またはそれ以上）に必要なものがすべて揃うまで、最短経路ツリーを開発し続けます。
次に、ノードのセット[i年、j歳のマシン]があります。i年目にあなたの会社に最適なものを見つけるには、その可能性をすべて調べて（[i年目、機械なし]になると思います）、答えを見つけてください。
ダイクストラは全ペア最短経路アルゴリズムであるため、すべての年へのすべての最良の経路を提供します
編集：最初にJavaの擬似コードを作成して、ノード情報を保持するノードオブジェクト/クラスを作成する必要があります。
Node{
int cost;
int year;
int ageOfMachine;
}
次に、ノードを追加して解決するだけです。PQがコストフィールドに基づいてノードをソートしていることを確認してください。ルートから開始：
PQ<Node> PQ=new PriorityQueue<Node>();
Node root= new Root(0,0,-1);//0 cost, year 0 and no machine)
PQ.offer(root);
int [] best= new int[years+1];
//set best[0..years] equal to a very large negative number
while(!PQ.isEmpty()){
Node n=PQ.poll();
int y=n.year;
int a=n.ageOfMachine;
int c=n.cost;
if(already have a cost for year y and machine of age a)continue;
else{
add [year y, age a, cost c] to list of settled nodes;
//examine all possible further actions
//add nodes for keeping a machine and trading a machine
PQ.offer(new Node(cost+profit selling current-cost of new machine,year+1,1));
PQ.offer(new Node(cost,year+1,age+1);//only if your machine can last an extra year
//check to see if you've found the best way of business in year i
if(cost+profit selling current>best[i])best[i]=cost+profit selling current;
}
}
それらの線に沿った何かがあなたに最高のコストでi年に到達するためのベストプラクティスを与えるでしょう[i]
