我无法理解棘手的编程问题

Question

首先，我要说的是，这不是作业（我是一名 A-Level 学生，这与我们解决的问题完全不同（这方式更难）），而是我遇到的一个问题。我正在努力改进我的编程逻辑。

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

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

输出将是：

36 + 3 + 5 = 44

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

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

我不是在寻找完整的代码或完整的算法，我只是想听听您对我应该如何进行此操作的意见，也许还可以分享一些技巧或其他东西。我今晚可能会开始做这件事。 :P

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

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

Answer 1

您正在查看背包问题

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

---

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

Answer 2

子集和可以吗？ ;]

Answer 3

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

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

Answer 4

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

Answer 5

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

我会对数组进行排序并给定输入总和m，会发现数组中第一个小于 m 的数字，将其称为 n（这是总和的第一个可能的数字），并从最大可能的补码开始 (mn），按你的方式向下工作。

如果您没有找到精确匹配，请选择可用的最高值，将其命名为 o（现在是您的第二个数字），然后查找从 (mno），然后再次向下移动。

如果未找到精确匹配，请从下一个数字 n（原始 n 的索引位于索引-1 处）开始，并执行相同的操作。您可以继续这样做，直到找到两个数字的精确匹配。如果未找到两个数字之和的匹配项，请重新开始该过程，但将其扩展以包含第三个数字。等等。

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

但有可能，最坏的情况是，你最终会经历这一切。

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

Answer 6

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

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 解决方案变得更慢。

Answer 7

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

Answer 8

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

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

Answer 9

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

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

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

问候。

Answer 10

好吧，我写了一个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 中，工作正常:-)