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

Question

我在一场现已结束的比赛中遇到了这个问题。我们有三种类型的硬币A，B和C，它们有一些与之相关的值，并且有N个商店。我们必须从这些商店收集N型硬币A，B，C，这样我们就可以选择A型的X硬币，B型的Y币和C型的Z币。我们也可以从商店中挑选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 * | stores |）。在我的代码中，我假设X + Y + Z = N，但是可以很容易地改变以解决X + Y + Z <= N的更一般情况。

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

值得一提的是，此代码找到了OPTIMAL解决方案。使用某种启发式方法可能会更有效率，但您必须放弃寻找最佳解决方案。

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