0

加算問題の再帰的解法に問題があります。問題は次のとおりです。与えられた m と n に対して、最小数が使用されるように n 個の数を m に合計するプログラムを作成します。ユーザーは n、m、n の数字を入力します。例: m=19 n=4 8,5,4,1 . 解は 8+5+5+1 です。配列内の次の数値で関数を呼び出し、合計よりも小さいうちに追加すると、配列内の次の数値の合計が m になる場合にのみ解が見つかります。問題が次のような場合: m=28 n=3 8,7,5 解決策は 8+8+7+5 ですが、私のプログラムは 8+8+8 になり、7 または 5 を追加しようとしてクラッシュします。それらのうち、最大 28 に収まる可能性があります。したがって、ここでの問題は、2 ステップ以上前に戻ることです。8+8+8+7 から 8+8+8 に変更できますが、8+8 に戻ることはできません。これはナップザック問題に似ていますが、より単純です。これまでに私のコードを含めて申し訳ありません：

#include <iostream>
#include <vector>
using namespace std;

void outputt(vector<int>);

int x(int m,vector<int> s,int n,int u)
{
    static int sum=0;
    static int level=0;
    static vector<int> p;
    sum+=s[u];       
    p.push_back(s[u]);

    if(level==((n-u)+1))
    {
        p.pop_back();
        level=0;
        x(m,s,n,u-1);
    }

    if(sum>m)
    {
        level++;
        sum-=s[u];
        p.pop_back();
        x(m,s,n,u+1);
    }

    if(sum==m)
    {
        outputt(p);
        return sum;
    }
    else
        x(m,s,n,u);

    level++;
    if(level>n-1)
        outputt(p);

    if(sum==m)
        return sum;
    else
    {
        cout<<"....";
        x(m,s,n,level);
    }
}

void outputt(vector<int> x)
{
    for(vector<int>::iterator i=x.begin();i!=x.end();++i)
        cout<<*i<<" ";
}

int main()
{
    int m,n;
    cin>>m>>n;
    int z;
    vector<int> p;
    for(int i=0;i<n;++i)
    {
        cin>>z;
        p.push_back(z);
    }
    cout<<x(m,p,n,0);

    system("PAUSE");
}

出力に問題がありますが、それは今のところ重要ではありません。

4

2 に答える 2

0

これは、必要な場所から遠く離れているわけではありません。これにより、最も浅いソリューションではなく、可能な限り迅速に (反復回数が最も少なく) ソリューションが見つかります。

#include <deque>
#include <iostream>
#include <iterator>
#include <algorithm>

template <typename IT, typename IT2>
bool perm_find(int num, IT start, IT last, IT2 output)
{
    for(IT first=start; first!=last; ++first)
    {
        int t=num-*first;
        if(t==0
        ||(t>0 && perm_find(t, start, last, output)))
        {   
            *output++=*first;
            return true;
        }   
    }
    return false;
} 

int main()
{
    int num;
    std::deque<int> pallet, results;

    std::cout << "Enter M: "      << std::endl;
    std::cin  >> num;
    std::cout << "Enter N vals: " << std::endl;

    std::copy(std::istream_iterator<int>(std::cin),
              std::istream_iterator<int>(),
              std::back_inserter(pallet));

    std::sort(pallet.rbegin(), pallet.rend());

    perm_find(num, pallet.begin(), pallet.end(), 
              std::back_inserter(results));

    std::copy(results.begin(), results.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    return 0;
}

可能な限り最短になるように変更するには、dijstras algo などを使用してすべての有効な組み合わせを調べる必要があります。

EDTT: バグがありましたが、現在修正済みです

于 2012-03-09T12:02:44.647 に答える
0

いくつかの提案:

  • 再帰コードの静的を避け (デバッグに使用できます)、関数の各インスタンスを可能な限り独立させます。
  • 関数 (x) 内のすべての数値 (s) をループして、最適解に戻ります。
  • とにかく変更されないため、数値を const 参照として渡します。
  • また、既に選択された数字 (試行) を含むコンテナーを (値として) 渡すため、戻るときに、前の試行 (バックトラック) を続行します。これが実際の状態です。
  • 合計は std::accumulate(attempt.begin(), attempts.end(), 0); です。
  • レベルは attempts.size(); です。
  • 最初に数字を降順に並べ替えて、最小数を取得します。
  • 後で必要な場合は試行ベクトルを返します (現在、常に合計を返すとは限りません)。
于 2012-03-09T12:52:40.283 に答える