类似于Knapsack Java代码的动态编程算法

Question

任务关键型生产系统有n个阶段,必须按顺序执行; 阶段i由机器M_i执行.

每个机器M_i具有可靠地运行的概率r_i和失败的概率1-r_i(并且故障是独立的).因此,如果我们用一台机器实现每个阶段,整个系统工作的概率是r_1,r_2,...,r_n.为了提高这种可能性,我们通过使用执行阶段i的机器M_i的m_i个副本来添加冗余.

所有m_i拷贝同时失败的概率仅为(1-r_i)^(m_i),因此阶段i正确完成的概率为1-(1-r_i)^(mi),整个系统工作的概率为PROD(I = 1,N){1-(1-R_I)^(M_I)}.

每台机器M_i的成本为c_i,购买机器的总预算为B. (假设B和c_i是正整数.)在给出概率r_1,...,r_n,成本c_1,...,c_n和预算B的java代码中写入算法,找到冗余m_1,... .,m_n在可用预算范围内,并最大化系统正常工作的概率(确定可实现的最大可靠性).此外,还要显示每种类型的机器在预算范围内达到可靠性的程度.

所以我读了一个文件,它给了我允许的总预算,然后是机器的数量,然后我读到的每台机器的成本和可靠性.我将成本和可靠性存储在两个链表中(不确定这是否最好).

  try {
            BufferedReader newFileBuffer = new BufferedReader(new     FileReader(inputFile));
            budget = Integer.parseInt(newFileBuffer.readLine()); 
            numberOfMachines = Integer.parseInt(newFileBuffer.readLine()); 
            while ((fileLine  = newFileBuffer.readLine()) != null) 
            {       
                line = fileLine.split(" ");

                try 
                {
                    cost.add(Integer.parseInt(line[0]));
                    totalCostOfOneEach += Integer.parseInt(line[0]); 
                    reliability.add(Float.parseFloat(line[1]));
                } catch (NumberFormatException nfe) {};

            }
            newFileBuffer.close();
        } catch (Exception e) 
        {
            e.printStackTrace();
        }

从那里我知道每台机器中的一台必须使用一次,所以我按每台机器之一(totalCostOfOneEach)的总成本减去预算,如果你愿意,这会让我超出预算或冗余预算.

bRedundent = (budget - totalCostOfOneEach);

现在是我被卡住的地方,我迷失了什么循环找到解决方案.我已经研究并找到了这个解决方案,但我不明白这条线

Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k}

所以我所知道的是我创建了一个双数组并且我将数组初始化为:

double[][] finalRel = new double[numberOfMachines][bRedundent]; 
for (int j = 0; j < numberOfMachines; j++)
{
    finalRel[0][j] = 0; 
}

for (int b = 1; b < budget; b++)
{
    finalRel[b][1] = reliability.get(0); 
}

现在是我被困的地方,我相信我应该循环机器的数量,然后成本,但这不起作用,我知道我需要以某种方式纳入预算.所以这就是我目前所拥有的根本不起作用的东西:

for (int i = 1; i < numberOfMachines; i++)
{
    for (int c = cost.get(i); c < budget; c++)
    {
        finalRel[i][c] = Math.min(finalRel[i-1][c], finalRel[i-1][c - cost.get(numberOfMachines)]*(l));
    }   
} 

我知道子问题表示为finalRel [i,b],机器1,2,...的最可靠配置...,i(每台机器中至少有一台)在预算范围内可用.期望的答案是finalRel [n,B].

如果我们在预算之下再次发生,我们返回可靠性0(意味着不可能).如果我们超出预算(b = 0),但仍然需要购买机器(i> 0),我们返回0(假设所有ci> 0).如果i = 0,我们没有必须购买的机器,所以可靠性是1(如果它是0,那么一切都会乘以0,这是不好的).如果有剩余预算(b> 0)和剩余的机器购买(i> 0),我们尝试购买i型机器的所有可能性 - 我们必须购买至少m≥1,最多m≤b ≤(b/c_i)≤b≤B,其中.在每种情况下,剩余预算将为b - m·c_i.机器的最佳可靠性1 ,. ..,i - 1将是REL [i - 1,b - m·ci],需要乘以M_i的m个副本的贡献,(1 - (1 - ri)^ m)或在此总结.

我意识到这很多信息,但我已经被困了一段时间,所以任何帮助都表示赞赏.

Answer 1

您可以使用比这更简单的循环。对于i = 0, ..., n和b = 0, ..., B，我们令为给定预算下R(i, b)各阶段子管道的最大可靠性。基本情况是1iB

For b = 0, ..., B,
  R(0, b) = 1,

因为空的管道永远不会出现故障并且不需要任何成本。此后我们有了链接的递归，为了清楚起见我稍微重写了它：

For i = 1, ..., n,
  For b = 0, ..., B,
    R(i, b) = max {R(i-1, b - k*c_i) * (1 - (1-r_i)^k)
                   for k = 1, ..., floor(b/c_i)},

我们正在考虑购买的k舞台机器的数量是多少（定义机器是否完全可靠；您应该自己计算功率，然后强度减少到乘法，这可以解决这个问题并提高性能）。因素是带有机器的舞台的可靠性。该因素是在给定剩余预算的情况下前几个阶段的最大可靠性。该限制是总成本最高的舞台机器的最大数量。i0^0 = 1(1 - (1-r_i)^k)ikR(i-1, b - k*c_i)floor(b/c_i)ib