首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >购买策略的动态规划

问购买策略的动态规划
EN

Stack Overflow用户
提问于 2018-02-12 21:39:29
回答 2查看 1.9K关注 0票数 3

假设有s_1,s_2,...,s_n苹果卖家,根据我们购买的数量,价格会有所不同,从卖方j购买苹果的价格是p(i,j)。找到一种以最低成本买苹果(0 <= A <= kn)的方法是什么?我认为开发动态规划算法需要建立一个M*n表,但不知道如何设计它。而且,我认为时间复杂度应该是O(n^2k^2),对吗?

后续问题:如果我们从卖方j购买u苹果,我们就不能从它的邻居(s_j-1和s_j+1)那里购买u+2或更多的苹果,在这种情况下,我们应该如何设计算法?

谢谢

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-02-12 22:12:14

这个问题很好地转化为常见的背包问题,只不过对于每个“项目”,您有许多不同的“价格”和“权重”,即您的p(i,j)函数。

从维基百科页面中无耻地复制的标准DP算法如下所示:

代码语言:javascript
复制
// Input:
// Values (stored in array v)     -> represented by p function
// Weights (stored in array w)    -> determined by parameter to p
// Number of distinct items (n)   -> different apple suppliers
// Knapsack capacity (W)          -> desired number of apples A

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

不过,有几个不同之处:

  • 您不是在寻找max值,而是在寻找min价格。
  • 你买不到W苹果,但确切地说是W苹果(否则,最好的策略是不买任何苹果)
  • 因此,没有零行;相反,您的第一行包含按相应大宗价格从供应商1购买的所有苹果。
  • 您必须考虑到p(i, j)的不同值

因此,您可以将算法调整到类似这样的情况(使用类似Python的列表理解符号)。

代码语言:javascript
复制
for j from 0 to W do:      // apples to buy from seller 1
    m[1, j] := p(1, j)

for i from 2 to n do:      // loop sellers 2 to n
    for j from 0 to W do:  // loop total number of apples to buy
        m[i, j] := min(m[i-1, j-k] + p(k, i) 
                       for k from 0 to j)  // apples bought from seller i

这意味着您有三个嵌套循环,这使其复杂性为O(NA 2)。

第二部分有点棘手,我不确定我是否真的明白了。基本上,这意味着对于每个卖家(第一个除外),你只能多买一个,同样的号码,或者比以前的卖家少一个。为此,您必须扩展DP矩阵,使之具有第三维度,即从卖方那里购买的苹果数,并将min表达式替换为实际循环,分配给该表的不同单元格。

票数 2
EN

Stack Overflow用户

发布于 2018-02-12 21:58:54

问题1所需的数据结构是,对于1..n中的每个1..n和0..A中的k,您可以从第一个j供应商那里购买k苹果的最低金额,以及您从最后一个供应商那里购买的苹果数量。如果为单个供应商计算,考虑到最后一个供应商,则需要对每个O(A) counts. Do that fornvendors and you needO(A^2*n)time. With some cleverness, you can also make itO(A^2)`内存进行O(A)操作。

对于问题2,它变得更加棘手。与通过供应商j购买的苹果数量相比,数据结构必须是每个(j, k)的数据结构,因为这关系到您购买多少苹果。现在是O(A^3*n)时间了。(其实比这更好,因为你从不从任何一个供应商那里买太多的苹果。)

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/48755937

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档