Лучший способ найти самое длинное расстояние, которое вы могли бы пройти, учитывая стоимость - PullRequest
Новая
       28

Лучший способ найти самое длинное расстояние, которое вы могли бы пройти, учитывая стоимость

0 голосов
/ 24 июня 2019

Предположим, у вас есть граф вершин.Каждая вершина имеет стоимость в долларах, чтобы путешествовать туда, но также и награду в биткойнах за ее посещение.Каждая вершина имеет ребро для любой другой вершины, а также для себя. стоимость поездки в данную вершину одинакова, будь то от нее или от любой другой вершины.Награда за путешествие в данную вершину одинакова, будь то от самой себя или от любой другой вершины.Пример:

Вершина A: стоимость посещения составляет 20 долларов США, награда - 25 биткойнов.

Вершина B: Стоимость посещения составляет 15 долларов США, награда - 19 биткойнов.

Вершина CСтоимость посещения - 6 долларов, награда - 7 биткойнов.

Я могу начать с любой вершины с N долларов.Я хочу получить как можно больше биткойнов за мои доллары.Если у меня есть 41 доллар, то в приведенном выше примере я могу получить 51 биткойн, посетив A, B, C ровно один раз в любом порядке.Если у меня будет 40 долларов, я смогу получить 50 биткойнов, дважды посетив A.

Я попытался решить эту проблему методом грубой силы 

#include <iostream>
#include <tuple>
#include <iterator>
#include <list>
#include <vector>

struct vertex_t
{
    int dollar_cost = 0;
    int bitcoin_reward = 0;
};

int try_visit_vertex(int& dollars, const vertex_t& vertex)
{
    if (dollars >= vertex.dollar_cost)
    {
        dollars -= vertex.dollar_cost;
        return vertex.bitcoin_reward;
    }
    return 0; // couldn't visit
}

auto enumerateVertices(const std::tuple<int, int>& status, const std::vector<vertex_t>& vertices)
{
    std::list<std::tuple<int, int>> bitcoinsObtainedAndDollarsRemaining;
    for (auto& vertex : vertices)
    {
        auto dollars_remaining = std::get<1>(status);
        const auto bitcoinsObtained = try_visit_vertex(dollars_remaining, vertex);
        if (bitcoinsObtained)
            bitcoinsObtainedAndDollarsRemaining.push_back(std::make_tuple(std::get<0>(status) + bitcoinsObtained, dollars_remaining));
    }
    return bitcoinsObtainedAndDollarsRemaining;
}

int most_bitcoins(const int dollars, const std::vector<vertex_t>& vertices)
{
    int maxBitcoinsObtained = 0;
    std::list bitcoinsObtainedAndDollarsRemaining = { std::make_tuple(0, dollars) };
    while (!bitcoinsObtainedAndDollarsRemaining.empty())
    {
        auto& front = bitcoinsObtainedAndDollarsRemaining.front();
        maxBitcoinsObtained = std::max(maxBitcoinsObtained, std::get<0>(front));
        auto backOfQueue = enumerateVertices(front, vertices);
        bitcoinsObtainedAndDollarsRemaining.pop_front();
        bitcoinsObtainedAndDollarsRemaining.splice(std::end(bitcoinsObtainedAndDollarsRemaining), backOfQueue);
    }

    return maxBitcoinsObtained;
}

int main()
{
    std::cout << most_bitcoins(41, { { 20, 25 }, { 15, 19 }, { 6, 7 } });
}

Я ищу кого-то более эффективного.Я подозреваю, что улучшением производительности было бы предотвращение дублирования при перечислении, например, если я push_back (A, A, B);Я не должен отталкиваться (A, B, A) или (B, A, A).Или, что еще лучше ... не нажимайте ни на какие дубликаты кортежей dollar_remaining + reward_amount.

...