棘手的编程问题，我困难地走了头
https://stackoverflow.com/questions/2320138
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
首先，让我说这不是作业（我是A级学生，这与我们问题所解决的问题无关（这就是 方法 ），但我想解决的更多问题以改善我的编程逻辑。
我想到了一个有一系列随机整数的场景，例如让我们说10个整数。用户将输入他要计算的数字，该算法将尝试确定需要哪些数字来制作该总和。例如，如果我想从这个整数数组中制作总和44：
myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);
输出将是：
36 + 3 + 5 = 44
或类似的规定。我希望我能清楚自己。作为额外的奖励，我想使算法选择尽可能少，以使所需的总和不需要，或者如果不能用所提供的数字键入该总和，则会给出错误。
我考虑过使用递归并在数组中迭代，一遍又一遍地添加数字，直到达到或过去。但是，我无法抓住我的头是如果算法超过总和，需要选择从数组中选择什么数字，该怎么办。
我不是在寻找完整的代码或完整的算法，我只想您对如何继续这样做的意见，也许是分享一些技巧或其他提示。今晚我可能会开始工作。 ：p
正如我说的，不是作业。只是我想做一些更先进的事情。
感谢您提供的任何帮助。 :)
其他提示
将要 子集总和 做？ ;
您的问题与 子集总和问题。在最坏情况下，您必须尝试所有可能的组合。
恐怕这里没有捷径。除了其他人所说的关于这是什么特定问题等的话，这里还有一些实用建议，可以为您提供一个起点：
我会排序数组并给出输入和 m, ，在数组中找到的第一个数字小于 m, ， 叫它 n （这是您的第一个可能的总数），然后从最高的补充开始（m-n），努力下降。
如果您找不到精确的匹配，请选择最高可用的匹配项，请致电 o, ，（那是您的第二个数字），然后从（从m-n-o）并再次努力。
如果您找不到精确的匹配，请从下一个数字n（index-1的原始n索引）开始，然后执行相同的操作。您可以继续执行此操作，直到找到两个数字的精确匹配为止。如果未找到两个数字的总和匹配，请再次开始该过程，但将其扩展到包括第三个数字。等等。
可以递归地完成。至少这种方法可确保当您找到匹配时，它将是构成总输入总和的集合中最小数字的方法。
不过，最糟糕的是，您最终会经历整个过程。
编辑: ：正如Venr正确指出的那样，我的第一种方法是不正确的。编辑的方法来反映这一点。
对于此问题，有一种非常有效的随机算法。我知道您已经接受了答案，但是无论如何我都很高兴分享，我只是希望人们仍然会检查这个问题:)。
Let Used = list of numbers that you sum.
Let Unused = list of numbers that you DON'T sum.
Let tmpsum = 0.
Let S = desired sum you want to reach.
for ( each number x you read )
toss a coin:
if it's heads and tmpsum < S
add x to Used
else
add x to Unused
while ( tmpsum != S )
if tmpsum < S
MOVE one random number from Unused to Used
else
MOVE one random number from Used to Unused
print the Used list, containing the numbers you need to add to get S
这将比动态编程解决方案快得多，尤其是对于随机输入。唯一的问题是您无法可靠地检测到没有解决方案的何时（您可以让算法运行几秒钟，并且如果没有完成，则假设没有解决方案），并且不能确定您将获得解决方案选择最少的元素数量。同样，您可以添加一些逻辑以使算法继续进行，并尝试找到较少元素的解决方案，直到满足某些停止条件为止，但这会使它变慢。但是，如果您只对有效的解决方案感兴趣，并且有很多数字，并且所需的总和可能很大，那么这可能比DP算法更好。
这种方法的另一个优点是，它也将适用于无修改的负和理性数字，这对于DP解决方案是不正确的，因为DP解决方案涉及将部分总和用作数组索引，而索引只能是自然数。您当然可以使用Hashtables，但这将使DP解决方案甚至更慢。
我不知道这项任务是什么，但是看来这是一种 http://en.wikipedia.org/wiki/knapsack_problem.
嘿，我会播放“不完整的规格”卡（没人说数字不会超过一次！），并将其减少到“变更”问题。按减少顺序对数字进行排序，找到第一个小于您所需的总和，然后从您的总和中减去该数字（除法和剩余者可以加快速度）。重复直到总和= 0或不小于该总和。
为了完整性，您需要跟踪每个总和中的加起来数量，并且当然通过跟踪您使用的第一个数字，跳过该数字并使用其他数字重复该过程来生成其他序列。这将在（6 + 4）问题上解决（7 + 2 + 1）。
重复他人的答案：这是子集总和问题。它可以通过动态编程技术有效地解决。
尚未提及以下内容：问题是伪P（或弱意义上的NP完整）。
在s中（基于动态编程）的算法（基于动态编程）的存在（其中s为sum）和n（元素数）证明了这一主张。
问候。
好的，我写了一个C ++程序来解决上述问题。该算法很简单:-)
首先，以降序排列您拥有的任何数组（我已经用降级形式对数组进行了硬编码，但是您可以应用任何排序算法）。
接下来，我拿了三个堆栈N，POS和SUM。第一个存储可能找到可能的总和组合的数字，第二个保存数组的索引从哪里开始搜索，第三个存储元素的元素将为您提供您输入的数字。
该功能查找数组中最大的数字，该数字小于或等于输入的数字。如果是相等的，则只需将数字推到总和堆栈上即可。如果不是，则将遇到的数组元素推到总和堆栈（暂时），并找到搜索和遇到的数字之间的区别，然后执行递归。
让我举个例子： - 在{63,36,22,19,12,9,7,7,5,3,1}中找到44
前36位将被推到总和（最多小于44）44-36 = 8将被推入n（下一个要搜索的数字）7将以sum 8-7 = 1推入n 1将是总和
因此44 = 36+7+1 :-)
#include <iostream>
#include<conio.h>
using namespace std;
int found=0;
void func(int n[],int pos[],int sum[],int arr[],int &topN,int &topP,int &topS)
{
int i=pos[topP],temp;
while(i<=9)
{
if(arr[i]<=n[topN])
{
pos[topP]=i;
topS++;
sum[topS]=arr[i];
temp=n[topN]-arr[i];
if(temp==0)
{
found=1;
break;
}
topN++;
n[topN]=temp;
temp=pos[topP]+1;
topP++;
pos[topP]=temp;
break;
}
i++;
}
if(i==10)
{
topP=topP-1;
topN=topN-1;
pos[topP]+=1;
topS=topS-1;
if(topP!=-1)
func(n,pos,sum,arr,topN,topP,topS);
}
else if(found!=1)
func(n,pos,sum,arr,topN,topP,topS);
}
main()
{
int x,n[100],pos[100],sum[100],arr[10]={63,36,22,19,12,9,7,5,3,1},topN=-1,topP=-1,topS=-1;
cout<<"Enter a number: ";
cin>>x;
topN=topN+1;
n[topN]=x;
topP=topP+1;
pos[topP]=0;
func(n,pos,sum,arr,topN,topP,topS);
if(found==0)
cout<<"Not found any combination";
else{
cout<<"\n"<<sum[0];
for(int i=1;i<=topS;i++)
cout<<" + "<<sum[i];
}
getch();
}
您可以复制代码并将其粘贴到IDE中，工作正常:-)
