运行快速动态规划算法得到所有答案

Question

我怎样才能运行快速动态规划算法得到所有可能的答案。假设我们有 20 个条目，它只显示 1 行最佳答案，我希望它一直运行并显示其他条目，直到结果显示所有条目，并且不允许重复。太感谢了。真的很感激。这是代码：

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <utility>

using namespace std;

float W ,N; //N = olcu sayisi, W = profil boyu
vector<float> numbers; //stores the set of numbers

pair<float, multiset<float>> calc(float i, float j) //returns closest sum and best subset of the first i numbers for the target value j
{
    static map<pair<float, float>, pair<float, multiset<float>>> dp; //stores results to avoid repeated calculations

    pair<float, float> p(i, j); //pair for convenience

    if(i == 0) //base case
    {
        return make_pair(0, multiset<float>(
                                      {}));
    }

    auto findResult = dp.find(p);

    if(findResult != dp.end()) //check if already calculated
    {
        return findResult->second;
    }

    auto temp1 = calc(i - 1, j); //compute result if not using number

    if(numbers[i - 1] > j) //if current number is too big
    {
        return temp1;
    }

    auto temp2 = calc(i - 1, j - numbers[i - 1]); //compute result if using number
    temp2.first += numbers[i - 1];
    temp2.second.insert(numbers[i - 1]);

    pair<float, multiset<float>> result;
    if(temp1.first != temp2.first) //compare results and choose best
    {
        result = temp1.first > temp2.first ? temp1 : temp2;
    }
    else
    {
        result = temp1.second.size() < temp2.second.size() ? temp1 : temp2;
    }
    dp[p] = result;

    return result;
}

int main()
{
    cout << "sineklik sayisi: ";
    cin >> N;
    N = 2 * N;
    cout << "Profil olcusu: ";
    cin >> W;
    numbers.reserve(N); //avoid extra reallocations

    cout << "Olculeri giriniz: ";
    for(int i = 0; i < N; i++) //input loop
    {
        float temp;
        cin >> temp;
        numbers.push_back(temp);
    }

    pair<float, multiset<float>> result = calc(N, W); //calculate

    //output below
    cout << "The best possible sum is " << result.first << " Left behind is " << W - result.first << ", obtained using the set of numbers {";
    if(result.second.size() > 0)
    {
        cout << *result.second.begin();
        for(auto i = ++result.second.begin(); i != result.second.end(); i++)
        {
            cout << ", " << *i;
        }
    }
    cout << "}.\n";
}

Answer 1

编辑： 这是我较早的回答之一。那时我没有那么好，现在我知道有一个更简单、更快、更少 memory-consuming 的解决方案来解决这个问题。如果我们在 table 中计算 DP bottom-up，它只存储最接近的可能总和，我们可以稍后使用我们计算的 table 值递归地重建子集。

输出所有数字集的总和等于不大于目标值的最大可能总和且包含尽可能少的数字的解决方案：

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <utility>

using namespace std;

int N, W; //N = number of numbers, W = target sum
vector<int> numbers; //stores the set of numbers

pair<int, set<multiset<int>>> calc(int i, int j) //returns closest sum and best subset of the first i numbers for the target value j
{
    static map<pair<int, int>, pair<int, set<multiset<int>>>> dp; //stores results to avoid repeated calculations
    pair<int, int> p(i, j); //pair for convenience
    if(i == 0) //base case
    {
        set<multiset<int>> temp;
        temp.emplace();
        return make_pair(0, temp);
    }
    auto findResult = dp.find(p);
    if(findResult != dp.end()) //check if already calculated
    {
        return findResult->second;
    }
    auto temp1 = calc(i - 1, j); //compute result if not using number
    if(numbers[i - 1] > j) //if current number is too big
    {
        return temp1;
    }
    pair<int, set<multiset<int>>> temp2 = calc(i - 1, j - numbers[i - 1]), newtemp2; //compute result if using number
    newtemp2.first = temp2.first + numbers[i - 1];
    for(const auto k : temp2.second)
    {
        multiset<int> temp = k;
        temp.insert(numbers[i - 1]);
        newtemp2.second.insert(temp);
    }
    pair<int, set<multiset<int>>> *result;
    if(temp1.first != newtemp2.first) //compare results and choose best
    {
        result = temp1.first > newtemp2.first ? &temp1 : &newtemp2;
    }
    else if(temp1.second.begin()->size() != newtemp2.second.begin()->size())
    {
        result =
                temp1.second.begin()->size() < newtemp2.second.begin()->size() ? &temp1 : &newtemp2;
    }
    else
    {
        temp1.second.insert(newtemp2.second.begin(), newtemp2.second.end());
        result = &temp1;
    }
    dp.insert(make_pair(p, *result));
    return *result;
}

int main()
{
    cout << "Enter the number of numbers: ";
    cin >> N;
    cout << "Enter target sum: ";
    cin >> W;
    numbers.reserve(N); //avoid extra reallocations
    cout << "Enter the numbers: ";
    for(int i = 0; i < N; i++) //input loop
    {
        int temp;
        cin >> temp;
        numbers.push_back(temp);
    }
    pair<int, set<multiset<int>>> result = calc(N, W); //calculate
    //output below
    cout << "The best possible sum is " << result.first << ", which can be obtained using a set of "
            << result.second.begin()->size() << " numbers " << result.second.size()
            << " different ways:\n";
    for(const auto &i : result.second)
    {
        cout << '{';
        if(i.size() > 0)
        {
            cout << *i.begin();
            for(auto j = ++i.begin(); j != i.end(); ++j)
            {
                cout << ", " << *j;
            }
        }
        cout << "}\n";
    }
}

此解决方案不允许数字在输出中出现的次数超过它在输入中出现的次数。如果您只想允许一个数字在输出中出现一次，即使它在输入中出现多次，请将多重集 numbersleft 更改为一个集合。

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <utility>

using namespace std;

int N, W; //N = number of numbers, W = target sum
vector<int> numbers; //stores the set of numbers

pair<int, set<multiset<int>>> calc(int i, int j) //returns closest sum and best subset of the first i numbers for the target value j
{
    static map<pair<int, int>, pair<int, set<multiset<int>>>> dp; //stores results to avoid repeated calculations
    pair<int, int> p(i, j); //pair for convenience
    if(i == 0) //base case
    {
        set<multiset<int>> temp;
        temp.emplace();
        return make_pair(0, temp);
    }
    auto findResult = dp.find(p);
    if(findResult != dp.end()) //check if already calculated
    {
        return findResult->second;
    }
    auto temp1 = calc(i - 1, j); //compute result if not using number
    if(numbers[i - 1] > j) //if current number is too big
    {
        return temp1;
    }
    pair<int, set<multiset<int>>> temp2 = calc(i - 1, j - numbers[i - 1]), newtemp2; //compute result if using number
    newtemp2.first = temp2.first + numbers[i - 1];
    for(const auto k : temp2.second)
    {
        multiset<int> temp = k;
        temp.insert(numbers[i - 1]);
        newtemp2.second.insert(temp);
    }
    pair<int, set<multiset<int>>> *result;
    if(temp1.first != newtemp2.first) //compare results and choose best
    {
        result = temp1.first > newtemp2.first ? &temp1 : &newtemp2;
    }
    else if(temp1.second.begin()->size() != newtemp2.second.begin()->size())
    {
        result =
                temp1.second.begin()->size() < newtemp2.second.begin()->size() ? &temp1 : &newtemp2;
    }
    else
    {
        temp1.second.insert(newtemp2.second.begin(), newtemp2.second.end());
        result = &temp1;
    }
    dp.insert(make_pair(p, *result));
    return *result;
}

int main()
{
    cout << "Enter the number of numbers: ";
    cin >> N;
    cout << "Enter target sum: ";
    cin >> W;
    numbers.reserve(N); //avoid extra reallocations
    cout << "Enter the numbers: ";
    for(int i = 0; i < N; i++) //input loop
    {
        int temp;
        cin >> temp;
        numbers.push_back(temp);
    }
    pair<int, set<multiset<int>>> result = calc(N, W); //calculate
    //output below
    cout << "The best possible sum is " << result.first << ", which can be obtained using sets of "
            << result.second.begin()->size() << " numbers:\n";
    multiset<int> numbersleft;
    numbersleft.insert(numbers.begin(), numbers.end());
    for(const auto &i : result.second)
    {
        bool good = true;
        for(const int &j : i)
        {
            if(numbersleft.find(j) == numbersleft.end())
            {
                good = false;
                break;
            }
        }
        if(good)
        {
            for(const int &j : i)
            {
                numbersleft.erase(j);
            }
            cout << '{';
            if(i.size() > 0)
            {
                cout << *i.begin();
                for(auto j = ++i.begin(); j != i.end(); ++j)
                {
                    cout << ", " << *j;
                }
            }
            cout << "}\n";
        }
    }
}

运行快速动态规划算法得到所有答案

running fast dynamic programming algorithm to get all the answers

c++

optimization

mathematical-optimization