I came across this problem in a competition which is now over. We have three type of coins A,B and C with some value associated with them and there are N number of stores. We have to collect N coins of type A,B,C from these stores such that we can pick X coins of type A , Y coins of B type and z coins of type C type. Also we can pick only 1 coin from a store.
We need to collect coins in such a way that we have maximum profit.
Example:
first line represent number of stores
second line represent X,Y,Z. number of coins to pick of each type respectively(A,B,C)
next lines representing value of A,B,C coins present on that store
4
2 1 1
5 3 4
8 6 1
10 3 3
5 1 5
So output -> 26 (5 from first + 6 from second + 10 from third + 5 from fourth)
2 coins of type A(5 + 10)
1 coin of type B(6)
1 coin of type C(5)
How can we solve this problem. Is it a dynamic programming question ?
I have thought of applying backtracking but it will take large amount of time and space.
I have a solution with dynamic programming, and it is O( X * Y * Z * |stores| ). On my code I am assuming that X + Y + Z = N, but that can be easily change to address a more general case where X + Y + Z <= N.
The solution was able to find the correct answer for this specific instance. I hope that the competition is really over and this is not an answer to a problem from an on-going competition.
It is worth to mention that this code find the OPTIMAL solution. You can probably be more efficient with some heuristic, but you will have to give up on finding the Optimal solution.
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <array>
using namespace std;
long long solver(const int X, const int Y, const int Z, const vector< array<long long, 3> >& stores )
{
const int total_stores = (int) stores.size();
long long DP[X + 1][Y + 1][Z + 1][total_stores + 1];
// we will consider the stores indexed from [1, ..., total_stores ]
// DP[v1][v2][v3][i] -> Best way of selecting v1 coins of type A,
// v2 coins of type B
// v3 coins of type C
// and we can consider only the stores from [1, ..., i]
// Initializing DP
for(int x = 0; x <= X; ++x)
{
for(int y = 0; y <= Y; ++y)
{
for(int z = 0; z <= Z; ++z)
{
for(int i = 0; i <= total_stores; ++i)
{
DP[x][y][z][i] = 0;
}
}
}
}
// Computing the actual values
for(int x = 0; x <= X; ++x)
{
for(int y = 0; y <= Y && x + y <= total_stores; ++y)
{
for(int z = 0; z <= Z && x + y + z <= total_stores; ++z)
{
for(int i = x + y + z; i <= total_stores; ++i)
{
if( i == 0) continue;
// the values from vector are indexed from 0, but
// here we will index them from 1, so watch out!
DP[x][y][z][i] = DP[x][y][z][i - 1]; // We have the option of not using any coins from this specific store
if( x > 0) DP[x][y][z][i] = max( DP[x][y][z][i],
DP[x - 1][y][z][i - 1] + stores[i - 1][0]); // We can use the coin A from this store
if( y > 0) DP[x][y][z][i] = max( DP[x][y][z][i],
DP[x][y - 1][x][i - 1] + stores[i - 1][1]); // We can use the coin B from this store
if( z > 0) DP[x][y][z][i] = max( DP[x][y][z][i],
DP[x][y][z - 1][i - 1] + stores[i - 1][2]); // We can use the coin C from this store
}
}
}
}
return DP[X][Y][Z][total_stores];
}
int main()
{
vector< array<long long, 3> > stores;
stores.emplace_back(array<long long, 3>{5, 3, 4} );
stores.emplace_back(array<long long, 3>{8, 6, 1} );
stores.emplace_back(array<long long, 3>{10, 3, 3} );
stores.emplace_back(array<long long, 3>{5, 1, 5} );
const int X = 2;
const int Y = 1;
const int Z = 1;
cout << "value of the solution is = " << solver( X, Y, Z, stores ) << endl;
return 0;
}