问题可以通过动态规划方法或回溯来解决

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) 硬币

我们如何解决这个问题。是动态规划题吗？

我想过应用回溯，但会花费大量时间，而且space。

Answer 1

我有一个动态规划的解决方案，它是 O( X * Y * Z * |stores| )。在我的代码中，我假设 X + Y + Z = N，但可以很容易地更改它以解决更一般的情况，其中 X + Y + Z <= N.

该解决方案能够找到此特定实例的正确答案。我希望比赛真的结束了，这不是对正在进行的比赛的问题的回答。

值得一提的是这段代码找到了最优解。您可能可以通过一些启发式方法提高效率，但您将不得不放弃寻找最佳解决方案。

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

问题可以通过动态规划方法或回溯来解决

Problem can be solved by dynamic programming approach or backtracking

dynamic-programming

backtracking