假设有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或更多的苹果,在这种情况下,我们应该如何设计算法?
谢谢
发布于 2018-02-12 22:12:14
这个问题很好地转化为常见的背包问题,只不过对于每个“项目”,您有许多不同的“价格”和“权重”,即您的p(i,j)函数。
从维基百科页面中无耻地复制的标准DP算法如下所示:
// 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苹果(否则,最好的策略是不买任何苹果)p(i, j)的不同值因此,您可以将算法调整到类似这样的情况(使用类似Python的列表理解符号)。
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表达式替换为实际循环,分配给该表的不同单元格。
发布于 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)时间了。(其实比这更好,因为你从不从任何一个供应商那里买太多的苹果。)
https://stackoverflow.com/questions/48755937
复制相似问题