Проблема может быть решена с помощью подхода динамического программирования или возврата

Question

Я столкнулся с этой проблемой на соревновании, которое теперь закончено.У нас есть три типа монет A, B и C, с которыми связано определенное значение, и есть N магазинов.Мы должны собрать N монет типа A, B, C из этих магазинов, чтобы мы могли выбрать X монет типа A, Y монет типа B и z монет типа C.Также мы можем выбрать только 1 монету из магазина.

Нам нужно собирать монеты таким образом, чтобы у нас была максимальная прибыль.

Пример:

первая строка представляет числоиз магазинов

вторая строка представляет X, Y, Z.количество монет для выбора каждого типа соответственно (A, B, C)

следующие строки, представляющие ценность монет A, B, C, имеющихся в этом магазине

---

4

2 1 1

5 3 4

8 6 1

10 3 3

5 1 5

Итак, вывод-> 26 (5 с первого + 6 с второго + 10 с третьего + 5 с четвертого)

2 монеты типа A (5 + 10)

1 монета типа B (6)

1 монета типа C (5)

Как мы можем решить эту проблему.Это вопрос динамического программирования?

Я думал о применении обратного отслеживания, но это займет много времени и пространства.

Answer 1

У меня есть решение с динамическим программированием, и оно O (X * Y * Z * | store |). В моем коде я предполагаю, что X + Y + Z = N, но это легко изменить, чтобы обратиться к более общему случаю, когда X + Y + Z <= N. </p>

Решению удалось найти правильный ответ для этого конкретного экземпляра. Я надеюсь, что соревнование действительно закончено, и это не ответ на проблему продолжающегося соревнования.

Стоит отметить, что этот код находит ОПТИМАЛЬНОЕ решение. Вы, вероятно, можете быть более эффективными с некоторой эвристикой, но вам придется отказаться от поиска оптимального решения.

#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;
}