26

首先，让我说这不是家庭作业（我是一名 A-Level 学生，这与我们解决的问题没有什么关系（这更难）），而是我试图解决的更多问题改进我的编程逻辑。

我想到了一个场景，其中有一个随机整数数组，例如 10 个整数。用户将输入一个他想要计数的数字，算法将尝试计算出需要哪些数字来计算总和。例如，如果我想从这个整数数组中求和 44：

myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);

输出将是：

36 + 3 + 5 = 44

或类似的规定。我希望我说清楚。作为额外的奖励，我想让算法选择尽可能少的数字来获得所需的总和，或者如果无法使用提供的数字得出总和，则给出错误。

我考虑过使用递归并遍历数组，一遍又一遍地添加数字，直到总和达到或过去。但是我无法理解的是，如果算法超过了总和并且需要有选择地从数组中选择哪些数字，该怎么办。

我不是在寻找完整的代码或完整的算法，我只是希望您对我应该如何进行此操作提出意见，并可能分享一些提示或其他内容。我今晚可能会开始工作。:P

正如我所说，不是家庭作业。只是我想做一些更高级的事情。

感谢您提供的任何帮助。:)

4

10 回答 10

31

你在看背包问题

背包问题或背包问题是组合优化中的问题：给定一组项目，每个项目都有一个重量和一个值，确定要包含在集合中的每个项目的数量，以便总重量小于给定的限制，并且总值尽可能大。它的名字来源于一个被固定大小的背包限制并且必须用最有用的物品装满它的人所面临的问题。

编辑：您的特殊情况是子集和问题

于 2010-02-23T17:15:20.743 回答
10

子集总和会吗？;]

于 2010-02-23T17:14:33.527 回答
4

这是你会在大学级别的算法课程中看到的经典背包问题（或者至少我当时看到了）。最好在纸上解决这个问题，代码中的解决方案应该相对容易解决。

编辑：要考虑的一件事是动态编程。

于 2010-02-23T17:16:27.540 回答
2

您的问题与子集和问题有关。在最坏的情况下，您必须尝试所有可能的组合。

于 2010-02-23T17:18:50.490 回答
2

恐怕这里没有捷径。除了其他人所说的，关于这是什么具体问题等，这里有一些实用的建议可以为您提供一个起点：

我会对数组进行排序并给定输入 sum m，会在数组中找到第一个小于 的数字m，调用它n（这是求和的第一个可能的数字），然后从可能的最高补码 ( m-n) 开始，一路向下.

如果您没有找到精确匹配，请选择最高可用的，调用它o，（现在是您的第二个号码）并从 ( ) 开始寻找第三个，m-n-o然后再次向下工作。

如果找不到精确匹配，请从下一个数字 n（原始 n 在 index-1 处的索引）开始并执行相同操作。您可以继续这样做，直到找到两个数字的精确匹配。如果两个数字的总和没有匹配，请再次启动该过程，但将其扩展为包含第三个数字。等等。

这可以递归地完成。至少这种方法可以确保当您找到匹配项时，它将是集合中可能的数字最少的那个，形成总输入总和。

不过，在最坏的情况下，你最终可能会经历所有的事情。

编辑：正如文尔正确指出的那样，我的第一种方法是不正确的。编辑方法以反映这一点。

于 2010-02-23T17:32:34.977 回答
2

对于这个问题，有一个非常有效的随机算法。我知道您已经接受了答案，但无论如何我很乐意分享，我只是希望人们仍然会检查这个问题:)。

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 解决方案涉及使用部分和作为数组索引，并且索引只能是自然数。例如，您当然可以使用哈希表，但这会使 DP 解决方案变得更慢。

于 2010-02-23T19:42:00.687 回答
1

我不知道这个任务到底叫什么，但它似乎有点像 http://en.wikipedia.org/wiki/Knapsack_problem。

于 2010-02-23T17:15:42.133 回答
1

嘿，我会玩“不完整的规范”牌（没有人说数字不能出现多次！）并将其简化为“做出改变”的问题。按降序对数字进行排序，找到第一个小于所需总和的数字，然后从总和中减去（除法和余数可以加快计算速度）。重复直到 sum = 0 或找不到小于总和的数字。

为了完整起见，您需要跟踪每个总和中的加数数量，当然，通过跟踪您使用的第一个数字、跳过该数字并使用附加数字重复该过程来生成附加序列。这将解决 (7 + 2 + 1) 超过 (6 + 4) 的问题。

于 2010-02-23T18:12:14.093 回答
1

重复其他人的答案：这是一个子集和问题。它可以通过动态规划技术有效地解决。

以下尚未提及：问题是伪P（或弱意义上的NP-Complete）。

S（其中 S 是总和）和 n（元素的数量）中存在算法（基于动态规划）多项式证明了这一主张。

问候。

于 2010-02-23T21:50:39.997 回答
0

好的，我写了一个C++程序来解决上面的问题。算法很简单:-)

首先按降序排列你拥有的任何数组（我已经以降序对数组进行了硬编码，但你可以应用任何排序算法）。

接下来我拿了三个栈 n、pos 和 sum。第一个存储要找到可能的总和组合的数字，第二个保存数组的索引，从哪里开始搜索，第三个存储元素，其相加将为您提供输入的数字。

该函数在数组中查找小于或等于输入数字的最大数字。如果相等，它只是将数字压入总和堆栈。如果不是，则将遇到的数组元素（临时）推送到和堆栈，并找到要搜索的数字与遇到的数字之间的差异，然后执行递归。

让我举个例子：- 在 {63,36,22,19,12,9,7,5,3,1} 中找到 44

前 36 将被推入总和（小于 44 的最大数字） 44-36=8 将被推入 n（下一个要搜索的数字） 7 将被推入总和 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 中，工作正常 :-)

于 2014-10-23T10:50:41.393 回答