CODEWITHSUNDEEP
algorithmdata-structuresdynamic-programming
coderx
coderx

Reputation: 519

Minimum cost of choosing items from n buckets

I have n numbers of buckets. Each bucket contains 3 items - say I1, I2 & I3. Each item has their own cost associated. You have to pick items from each bucket such that items picked from 2 consecutive buckets are not same. What will be the algorithm to find minimum cost of picking n items from n such buckets?

I can think only recursive brute force solution which will explore all costs and find out the minimum of them.

What can be the efficient algorithm to solve the problem?

Upvotes: 2

Views: 260

Answers (1)

Codor
Codor

Reputation: 17605

The state space for dynamic programming can be defined as follows.

C[i,j] = minimum cost attainable by choosing items an item from each
         bucket in {1,...,i} where each item index is different from
         the item index in the previous bucket and the item in the
         last bucket is j where i in {1,...,n} and j in {1,2,3}

For this state space, we obtain the following recurrence relation, where I[j,k] for each j in {1,...,n} and k in {1,2,3} denotes the cost of the k-th item in bucket k.

C[i,j] = min { min { C[i-1,2], C[i-1,3] } + I[i,1]: j = 1,
               min { C[i-1,1], C[i-1,3] } + I[i,2]: j = 2,
               min { C[i-1,1], C[i-1,2] } + I[i,3]: j = 3
             }

The initial states can be filled by assigning

C[1,1] = I[1,1],
C[1,2] = I[1,2],
C[1,3] = I[1,3]

and after iteratively filling the state space, the desired value can be found by evaluating the folowing expression.

min { C[n,1], C[n,2], C[n,3] }

Upvotes: 1

Related Questions