すべての答えを得るために高速動的計画法アルゴリズムを実行する

編集：これは私の古い答えの1つです。当時はそれほど上手ではありませんでしたが、今では、この問題に対してはるかに簡単で、高速で、メモリ消費の少ないソリューションがあることがわかりました。可能な限り最も近い合計のみを格納するテーブルでDPボトムアップを計算する場合、計算したテーブル値を使用して、後で再帰的にサブセットを再構築できます。

合計が目標値以下の可能な最大の合計に等しく、可能な限り少ない数の数値を含むすべての数値のセットを出力するソリューション：

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

このソリューションでは、入力に表示された回数よりも多くの数値が出力に表示されることはありません。入力に複数回表示された場合でも、出力に1回だけ表示されるようにする場合は、マルチ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";
        }
    }
}