首先，我正在寻找简单易懂的东西，而不是最有效的。
我正在尝试创建一个函数，该函数将接受vector和int。该函数应返回true如果向量中的任何数字可以加起来为 int。
向量将以其中1,2,3,4,5,6,7,8,9,10的数字开头，并在整个程序中删除数字。不会有重复的数字。
int可以是 2 到 12 之间的任何数字。
一些例子：
-
vector = { 2,3,4,5 } int = 7;函数返回true，因为3 + 4 = 7。 -
vector = { 1,5,8 } int = 7;函数返回false因为这些数字都不能加到 7。 -
vector = { 3,6 } int = 3;函数返回true，因为3 = 3。 -
vector = { 5 } int = 2;函数返回false因为 5 不能加到二。
这是我完成正在开发的游戏所需的最后一个功能。我觉得我错过了一个简单的解决方案，但我不确定。谁能告诉我如何做到这一点，或者为我指出如何解决这个问题的正确方向？提前谢谢你。
鉴于注释中的附加信息，以下函数应该可以(我假设相同的数字不能在总和中使用两次(：
typedef std::vector<int>::iterator iter;
bool contains_sum(iter begin, iter end, int sum)
{
while (begin != end)
{
--end;
if (*end > sum)
continue;
if (contains_sum(begin, end, sum - *end))
return true;
}
return sum == 0;
}
背包问题的情况吗？
另请参阅：子集和
您需要做的是找到所有可能的组合，然后检查其中是否有任何组合具有正确的总和。双递归函数可以进行检查。
bool canFormSum(vector<int>::iterator rest, vector<int>::iterator end,
int sumSoFar, int targetSum)
{
if(rest == end) return false;
if(sumSoFar + *rest == targetSum) return true;
if(canFormSum(rest + 1, end, sumSoFar, targetSum)) return true;
if(sumSoFar + *rest > targetSum) return false;
return canFormSum(rest + 1, end, sumSoFar + *rest, targetSum);
}
这是递归计算的一个很好的例子 - 但对于除了小向量之外的任何东西，它的性能都很糟糕。
对于一般情况(向量的大小> 10(，
设f({a, b, c, d, ...}, e)集合中的任何数字是否{a, b, c, d, ...}等于 e 的结果。
观察，如果e = x + y + z + ...，则 (1( a 在{x, y, z, ...}集合中，或 (2( a不在{x, y, z, ...}集合中。这意味着，我们有递归定义：
f({a, etc...}, e) = f({etc...}, e-a) || f({etc...}, e)
显然，如果总和为 0，则通过不包含集合中的任何元素，关系始终为真：
f({...}, 0) = true
如果集合为空且总和为非零，则关系始终为假：
f({}, e) = false (if e != 0)
这些是递归的基本情况。
编辑：另请参阅子集和问题以进行进一步讨论。
只是为了将我的 (C( 解决方案与 celtschk (c++( 解决方案进行比较。(基本上比较的是方法，而不是语言(
#include <iostream>
#include <vector>
using namespace std;
int counter = 0;
typedef std::vector<int>::iterator iter;
bool contains_sum(iter begin, iter end, int sum)
{
counter ++;
while (begin != end)
{
--end;
if (contains_sum(begin, end, sum - *end))
return true;
}
return sum == 0;
}
int main () {
vector<int> data;
for (int i = 1; i <= 30; i ++) {
data.push_back(i);
}
int target = 77;
if (contains_sum (data.begin(), data.end(), target)) {
cout << "possiblen" << counter;
} else {
cout << "not possiblen << counter";
}
}
输出
possible
268304387
意味着近 2.7 亿次递归方法调用
现在我的方法
#include<stdio.h>
#include<stdlib.h>
int counter;
int check (int* in, int sum) {
counter ++;
while (1) {
int act = *in++;
if (act == 0) return 0;
int rest = sum - act;
if (rest == 0) return 1; // found;
if (rest > 0) {
if (1 == check (in, rest)) return 1; // found
}
}
return -1;
}
void pr (int* in, int sum) {
counter = 0;
int res = check (in, sum);
while (*in) {
printf ("%d ", *in ++);
}
if (res == 0) {
printf(" != %d %dn", sum, counter);
} else {
printf(" == %d %dn", sum, counter);
}
}
int main () {
int p0[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,
11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
0};
pr (p0, 77);
int p1[] = {2,3,4,5, 0};
pr (p1, 7);
int p2[] = {1,5,8, 0};
pr (p2, 7);
int p3[] = {3,6, 0};
pr (p3, 3);
int p4[] = {5, 0};
pr (p4, 2);
int p5[] = {1, 100, 6, 0};
pr (p5, 7);
return 0;
}
这是输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 == 77 22
2 3 4 5 == 7 4
1 5 8 != 7 4
3 6 == 3 1
5 != 2 1
1 100 6 == 7 2
Ups，只有 22 次迭代！任何人都可以决定哪种方法更"优雅">
您必须尝试所有可能的组合，直到找到解决方案。SUch问题对"prolog"语言有好处。所以我们必须模拟回溯。这段代码在最后是 C。
#include<stdio.h>
int check (int* in, int sum) {
while (1) {
int act = *in++;
if (act == 0) return 0;
int rest = sum - act;
if (rest > 0) { // test in the order of expected likelyhoods
if (1 == check (in, rest)) return 1; // found
}
// if (rest < 0) return 0; // minor optimization, valid if list is ordered ascendant
if (rest == 0) return 1; // found;
}
//return -1; // only necessary on poor compilers
}
void pr (int* in, int sum) {
int res = check (in, sum);
while (*in) {
printf ("%d ", *in ++);
}
if (res == 0) {
printf(" != %dn", sum);
} else {
printf(" == %dn", sum);
}
}
int main () {
int p1[] = {2,3,4,5, 0};
pr (p1, 7);
int p2[] = {1,5,8, 0};
pr (p2, 7);
int p3[] = {3,6, 0};
pr (p3, 3);
int p4[] = {5, 0};
pr (p4, 2);
int p5[] = {1, 100, 6, 0};
pr (p5, 7);
return 0;
}
经验证可运行
2 3 4 5 == 7
1 5 8 != 7
3 6 == 3
5 != 2
1 100 6 == 7