我在求和问题的递归解决方案中遇到问题。问题是:对于给定的 m 和 n,编写一个程序,将 n 个数字加总为 m,以便使用最小数字并且它们是。Id 有多个解决方案,正确的一个是使用更大数字的那个。用户输入 n,m 和 n 个数字。例如: m=19 n=4 8,5,4,1 。解决方案是 8+5+5+1。如果我用数组中的下一个数字调用函数并在其小于 sum 时添加它,则只有当数组中的下一个数字总和为 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");
}
输出有问题,但现在这并不重要。