我很难找到以下问题的解决方案。
假设一家公司需要在未来五年内拥有一台机器。每台新机器的成本为 100,000 美元。一台机器在第 i 年运行期间的年运行成本如下：C1 = 6000 美元，C2 = 8000 美元，C3 = 12,000 美元。一台机器在交易之前最多可以保留三年。这意味着机器可以在前两年保留或交易，并且必须在其三岁时交易。i 年后的价值交易是 t1 = 80,000 美元，t2 = 60,000 美元，t3 = 50,000 美元。如果公司打算在第 0 年购买一台新机器，公司如何在五年期间（第 0 年到第 5 年）将成本降至最低？
设计基于动态规划的最优解。
这个问题可以用树来表示。这是图表。
现在我认为在上述树中找到最短路径将为我提供最佳解决方案。但我不知道该怎么做。以下是我的问题，
也欢迎任何其他建议。
伙计们，我需要一些关于这个问题的指导和帮助。（不要认为这是要求你完成我的作业。）我在这里找到了这个问题的完整 Java 实现。但它没有使用动态规划来解决问题。先感谢您。
该公司希望在 5 年内将成本降至最低。在第 0 年，他们将购买一台机器，并且每年他们必须决定该机器是保留还是交易。为了达到最佳解决方案，我们必须在每年年底做出一系列选择。当我们做出每个选择时，经常会出现相同的子问题。因此，我们到达了一个位置，即给定的子问题可能来自多个部分的选择集。在设计基于动态规划的最优解时，我们可以通过结合子问题的解来解决问题。
让阶段对应于每年。状态是该年机器的年龄。决定是保留机器还是以旧换新。设 Ft(x) 是从时间 t 到时间 5 产生的最小成本，假设机器在时间 t 内使用了 x 年。 基本情况：
由于我们必须在 5 年末交易机器 F5(x)=-S[x]
保留现有机器最多 3 年：Ft(3)=N+M[0]+Ft+1(0) ；t≠0,1,2
def Fxy（自我，时间，年龄）：
if self.Matrix[time][age]==None: <- Overlaping subproblems avoided if(time>5 or age>2): return 0 if time==5: self.Matrix[time][age]=T=self.S[age] self.Flag[time][age]='TRADE' elif time==0: self.Matrix[time][age]=K=self.N+self.M[0]+self.Fxy(time+1,time) self.Flag[time][age]='KEEP' elif time==3 and age==2: self.Matrix[time][age]=T=self.S[age]+self.N+self.M[0]+self.Fxy(time+1,0) self.Flag[time][age]='TRADE' else: T=self.S[age]+self.N+self.M[0]+self.Fxy(time+1,0) if age+1<len(self.Matrix[0]): K=self.M[age+1]+self.Fxy(time+1,age+1) else: K=self.M[age+1] self.Matrix[time][age]=min(T,K) if(self.Matrix[time][age]==T and self.Matrix[time][age]==K): self.Flag[time][age]='TRADE OR KEEP' elif(self.Matrix[time][age]==T): self.Flag[time][age]='TRADE' else: self.Flag[time][age]='KEEP' return self.Matrix[time][age] else: return self.Matrix[time][age]
可以通过绘制包含所有可能路径并采用最小成本路径的决策树来实现最佳解决方案。我们使用递归算法遍历每个树级别并制作当前决策点出现的路径。例如：当它穿过 F1(0) 时，它有 'TRADE OR KEEP' 决定与之绑定。然后我们可以遍历两条可能的路径。当它遍历 F2(1) 时，因为它有 'KEEP' 决定，所以我们递归地遍历 F3(2)，右孩子。当'TRADE'遇到时，左孩子不断地到达叶子。
def recursePath(self,x,y):
if(x==5):
self.dic[x].append(self.Flag[x][y])
return self.Flag[x][y]
else:
if(self.Flag[x][y]=='TRADE OR KEEP'):
self.recursePath(x+1,y)
self.recursePath(x+1,y+1)
if(self.Flag[x][y]=='KEEP'):
self.recursePath(x+1,y+1)
if(self.Flag[x][y]=='TRADE'):
self.recursePath(x+1,y)
self.dic[x].append(self.Flag[x][y])
return self.Flag[x][y]
我想我找到了一个更简单的动态程序解决方案。
Suggest Cost(n) 是在第 n 年销售时的总成本。而保持一台机器1、2、3年的成本为cost1,cost2,cost3（本题为26000、54000、76000）。
然后我们可以将问题划分为如下子问题：
**Cost(n)= MIN( Cost(n-1)+cost1, Cost(n-2)+cost2, Cost(n-3)+cost3 );**
所以我们可以用“自下而上的方式”来计算它，也就是 O(n)。
我已经使用 C 实现并测试了它：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct costAndSell_S{
int lastSellYear;
int cost;
};
int operatCost[3]={6000,8000,12000};
int sellGain[3]={80000,60000,50000};
int newMachinValue=100000;
int sellCost[3];
struct costAndSell_S costAndSell[20];
void initSellCost(){
memset( costAndSell, 0, sizeof(costAndSell));
sellCost[0]=operatCost[0]+newMachinValue-sellGain[0];
sellCost[1]=operatCost[0]+operatCost[1]+newMachinValue-sellGain[1];
sellCost[2]=operatCost[0]+operatCost[1]+operatCost[2]+newMachinValue-sellGain[2];
costAndSell[0].cost=100000;
return;
}
int sellAt( int year ){
if ( year<0){
return(costAndSell[0].cost );
}
return costAndSell[year].cost;
}
int minCost( int i1, int i2, int i3 ){
if ( (i1<=i2) && (i1<=i3) ){
return(0);
}else if ( (i2<=i1) && (i2<=i3) ){
return(1);
}else if ( (i3<=i1) && (i3<=i2) ){
return(2);
}
}
void findBestPath( int lastYear ){
int i;
int rtn;
int sellYear;
for( i=1; i<=lastYear; i++ ){
rtn=minCost( sellAt(i-1)+sellCost[0], sellAt(i-2)+sellCost[1], sellAt(i-3)+sellCost[2]);
switch (rtn){
case 0:
costAndSell[i].cost=costAndSell[i-1].cost+sellCost[0];
costAndSell[i].lastSellYear=i-1;
break;
case 1:
costAndSell[i].cost=costAndSell[i-2].cost+sellCost[1];
costAndSell[i].lastSellYear=i-2;
break;
case 2:
costAndSell[i].cost=costAndSell[i-3].cost+sellCost[2];
costAndSell[i].lastSellYear=i-3;
break;
}
}
sellYear=costAndSell[lastYear].lastSellYear;
printf("sellAt[%d], cost[%d]\n", lastYear, costAndSell[lastYear].cost );
do{
sellYear=costAndSell[sellYear].lastSellYear;
printf("sellAt[%d], cost[%d]\n", sellYear, costAndSell[sellYear].cost );
} while( sellYear>0 );
}
void main(int argc, char * argv[]){
int lastYear;
initSellCost();
lastYear=atoi(argv[1]);
findBestPath(lastYear);
}
输出是：
sellAt[5], cost[228000]
sellAt[3], cost[176000]
sellAt[0], cost[100000]
如果你想要像 Dijkstra 这样的东西，为什么不直接做 Dijkstra 呢？您需要在图形解释中更改一些内容，但这似乎非常可行：
Dijkstra 将根据最低成本标准结算节点。将该标准设置为“公司损失的钱”。您还将在 Dijkstra 解决节点，您需要确定究竟什么是节点。考虑一个节点是一个时间和一个属性状态，例如第 4 年和 x 年的工作机器。在第 0 年，损失的钱将是 0，您将没有机器。然后，您添加所有可能的边缘/选择/状态转换，这里是“购买机器”。您最终会在 Dijkstra PQ [第 1 年，第 1 年的工作机器] 上以一定的成本获得一个新节点。
从那时起，您可以随时出售机器（产生 [year 1, no machine] 节点），购买新机器 [year 1, new machine]）或继续使用相同的机器（[year 2, machine of age 2]） . 您只需继续开发最短路径树，直到获得第 5 年（或更多）所需的一切。
然后你有一组节点 [第 i 年，年龄 j 的机器]。要在第 i 年找到最适合贵公司的方案，只需在所有可能性中寻找它（我认为它永远是 [第 i 年，没有机器]）以获得您的答案。
由于 Dijkstra 是一种全对最短路径算法，它为您提供了所有年份的所有最佳路径
编辑：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]
您提供的链接是动态编程 - 代码很容易阅读。我建议好好看看代码，看看它在做什么。
我认为它不能使用动态编程，因为我找不到最佳子结构和重叠子问题。第 N 年的成本取决于第 N-1、N-2 和 N-3 年的行为。很难找到最优的子结构。
以下方法可能有效。
每年年底，你有两个选择。您可以选择交易或选择再支付一年的维护费用。除了第三年，你别无选择。你必须确定交易。
这可以通过递归方法来解决，您可以在交易中选择最低成本，而不是在特定年份进行交易。
可以为第 n 年（无交易）的偏移量维护一个表，以便无需重新计算值