dynamic programming for buying strategy

Question

Say there are s_1,s_2,...,s_n apple sellers, depending on the amount that we buy, the price will be different, and price of buying i apples from seller j is p(i, j). What is the strategy for finding a way to buy exactly A apples (0 <= A <= kn) with minimum cost? I think a M*n table is needed to be built for developing dynamic programming algorithm, but am not sure how to design it. Moreover, I think time complexity should be O(n^2 k^2) something, am I correct?

Follow-up question: if we buy u apples from seller j, we are not allowed to buy u+2 or more apples from its neighbors(s_j-1 and s_j+1), how should we design the algorithm in this case?

Thanks

Answer 1

This problem nicely translates to the common Knapsack problem, except that you have many different "prices" and "weights" for each "item" to account for, i.e. your p(i,j) function.

The standard DP algorithm, shamelessly copied from the Wikipedia page, looks like this:

// 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])

There are a few differences, though:

• you are not looking for the max value, but for the min price
• you can not buy up to W apples, but exactly W apples (otherwise, the best strategy would be not to buy any apples)
• consequently, there is no zeros-row; instead, your first row contains all the apples bought from supplier 1 at the corresponding bulk prices
• you have to account for the different values for p(i, j)

Thus, you can adapt the algorithm to something like this (using a Python-like list comprehension notation)

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

This means that you have three nested loops, though, giving this a complexity of O(nA²).

---

The 2nd part is a bit tricky, and I'm not sure I really understood it. Basically, this means that for each seller (except the first) you can only buy one more, the same number, or one less than from the previous seller. For this you'd have to extend the DP matrix to have a third dimension, the number of apples bought from that seller, and replace the min expression with an actual loop, assigning to different cells of that table.

Answer 2

The data structure that you need for problem 1 is, for each j in 1..n and k in 0..A, the minimum amount you can have spent to buy k apples from the first j vendors, along with how many you bought from the last one. Calculating that for a single vendor, given that you have it for the last, requires O(A) operations for each of O(A) counts. Do that fornvendors and you needO(A^2*n)time. With some cleverness, you can also make itO(A^2)` memory.

For problem 2 it becomes more tricky. Instead of a data structure per number of apples bought through vendor j, it has to be a data structure per (j, k) because it matters how many apples you buy. That makes it O(A^3*n) time. (Actually better than that, because you never buy too many apples from any one vendor.)