这个属于超递增的NP完全类问题

给你个思路。

排序，然后从大的数开始穷举。

最初由 menglv 发布
有30个不一样的数，请在一分钟内判断其中n个数的和为一个定值。

是不是这个意思：给定30个不同的数和一个定值N，然后求出n个数和为N的所有解。

如果是这样的话，排序后直接用回溯也就可以了。

嗯,理论上没有有效算法,时间复杂度O(2^m),只能通过各种剪枝来优化.不过只有30个数,一分钟出解应该是没问题的,试试下面我写的:

#include <stdio.h>
#include <stdlib.h>

int a[50],ans[50],sum[50],pans,n,solved;

int cmp(const void *a,const void *b)
{
	int *tmpa,*tmpb;
	tmpa = (int*)a;
	tmpb = (int*)b;
	return *tmpa - *tmpb;
}

void output()
{
	int i;
	printf("符合条件的数为：%d",a[ans[0]]);
	for (i = 1 ; i < pans ; i++)
		printf(" + %d",a[ans[i]]);
	printf("\n");
}

void solve(int p,int tot)
{
	int i;
	if (tot == 0)					//找到了解
	{
		solved = 1;
		output();
		return;
	}
	if (p == n) return;				
	if (tot > sum[p]) return;		//剩下的数全用上也不够，直接返回
	for (i = p ; i < n ; i++)
	{
		if (tot - a[i] < 0) break;	//最小的数都会超出，则直接返回
		ans[pans++] = i;			//记录结果
		solve(i+1,tot-a[i]);
		if (solved) return;			//如果找到解则直接返回
		ans[--pans] = 0;
	}
}

int main()
{
	int i,tot;
	printf("请输入数字的总个数：");
	scanf("%d",&n);
	printf("请依次输入每个数字：");
	for (i = 0 ; i < n ; i++)
		scanf("%d",&a[i]);
	printf("请输入数字的总和：");
	scanf("%d",&tot);
	qsort(a,n,sizeof(int),cmp);		//从小到大排序
	sum[n-1] = a[n-1];
	for (i = n-2 ; i >= 0 ; i--)
		sum[i] = sum[i+1] + a[i];	//sum[i]为从a[i]到a[n-1]的所有数之和，剪枝用
	solved = pans = 0;
	solve(0,tot);					//递归求解
	if (solved == 0) printf("无解\n");
	return 0;
}

btw: 如果那个给定的n比较小的话,可以直接开个大小为n的数组存储状态,这样也就算是DP了,复杂度O(mn),当n较小m较大时会比上面快得多,当然如果n大了就不行了.

高手，小弟用vb没用剪枝30个数就花去将近2分钟。你的程序很快，厉害！
这是小弟的代码，相当愚昧。
Private Sub Command1_Click()
Dim i0 As long
Dim i1 As long
Dim i2 As long
Dim i3 As long
Dim i4 As long
Dim i5 As long
Dim i6 As long
Dim i7 As long
Dim i8 As long
Dim i9 As long
Dim i10 As long
Dim i11 As long
Dim i12 As long
Dim i13 As long
Dim i14 As long
Dim i15 As long
Dim i16 As long
Dim i17 As long
Dim i18 As long
Dim i19 As long
Dim i20 As long
Dim i21 As long
Dim i22 As long
Dim i23 As long
Dim i24 As long
Dim i25 As long
Dim i26 As long
Dim i27 As long
Dim i28 As long
Dim i29 As long
Dim a0 As Double
Dim a1 As Double
Dim a2 As Double
Dim a3 As Double
Dim a4 As Double
Dim a5 As Double
Dim a6 As Double
Dim a7 As Double
Dim a8 As Double
Dim a9 As Double
Dim a10 As Double
Dim a11 As Double
Dim a12 As Double
Dim a13 As Double
Dim a14 As Double
Dim a15 As Double
Dim a16 As Double
Dim a17 As Double
Dim a18 As Double
Dim a19 As Double
Dim a20 As Double
Dim a21 As Double
Dim a22 As Double
Dim a23 As Double
Dim a24 As Double
Dim a25 As Double
Dim a26 As Double
Dim a27 As Double
Dim a28 As Double
Dim a29 As Double
Dim aa As Double
Dim aa1 As Double
Dim bb As String
Dim tt As Long
a0 = Val(Text1(0))
a1 = Val(Text1(1))
a2 = Val(Text1(2))
a3 = Val(Text1(3))
a4 = Val(Text1(4))
a5 = Val(Text1(5))
a6 = Val(Text1(6))
a7 = Val(Text1(7))
a8 = Val(Text1(8))
a9 = Val(Text1(9))
a10 = Val(Text1(10))
a11 = Val(Text1(11))
a12 = Val(Text1(12))
a13 = Val(Text1(13))
a14 = Val(Text1(14))
a15 = Val(Text1(15))
a16 = Val(Text1(16))
a17 = Val(Text1(17))
a18 = Val(Text1(18))
a19 = Val(Text1(19))
a20 = Val(Text1(20))
a21 = Val(Text1(21))
a22 = Val(Text1(22))
a23 = Val(Text1(23))
a24 = Val(Text1(24))
a25 = Val(Text1(25))
a26 = Val(Text1(26))
a27 = Val(Text1(27))
a28 = Val(Text1(28))
a29 = Val(Text1(29))
aa1 = Val(Text1(31))
For i29 = 0 To 1
For i28 = 0 To 1
For i27 = 0 To 1
For i26 = 0 To 1
For i25 = 0 To 1
For i24 = 0 To 1
For i23 = 0 To 1
For i22 = 0 To 1
For i21 = 0 To 1
For i20 = 0 To 1
For i19 = 0 To 1
For i18 = 0 To 1
For i17 = 0 To 1
For i16 = 0 To 1
For i15 = 0 To 1
For i14 = 0 To 1
For i13 = 0 To 1
For i12 = 0 To 1
For i11 = 0 To 1
For i10 = 0 To 1
For i9 = 0 To 1
For i8 = 0 To 1
For i7 = 0 To 1
For i6 = 0 To 1
For i5 = 0 To 1
For i4 = 0 To 1
For i3 = 0 To 1
For i2 = 0 To 1
For i1 = 0 To 1
For i0 = 0 To 1
    aa = a0 * i0 + a1 * i1 + a2 * i2 + a3 * i3 + a4 * i4 + a5 * i5 + a6 * i6 + a7 * i7 + a8 * i8 + a9 * i9 + a10 * i10 + a11 * i11 + a12 * i12 + a13 * i13 + a14 * i14 + a15 * i15 + a16 * i16 + a17 * i17 + a18 * i18 + a19 * i19 + a20 * i20 + a21 * i21 + a22 * i22 + a23 * i23 + a24 * i24 + a25 * i25 + a26 * i26 + a27 * i27 + a28 * i28 + a29 * i29
    If aa = aa1 Then
        bb = a0 & "*" & i0 & "+" & a1 & "*" & i1 & "+" & a2 & "*" & i2 & "+" & a3 & "*" & i3 & "+" & a4 & "*" & i4 & "+" & a5 & "*" & i5 & "+" & a6 & "*" & i6 & "+" & a7 & "*" & i7 & "+" & a8 & "*" & i8 & "+" & a9 & "*" & i9 & "+" & a10 & "*" & i10 & "+" & a11 & "*" & i11 & "+" & a12 & "*" & i12 & "+" & a13 & "*" & i13 & "+" & a14 & "*" & i14 & "+" & a15 & "*" & i15 & "+" & a16 & "*" & i16 & "+" & a17 & "*" & i17 & "+" & a18 & "*" & i18 & "+" & a19 & "*" & i19 & "+" & a20 & "*" & i20 & "+" & a21 & "*" & i21 & "+" & a22 & "*" & i22 & "+" & a23 & "*" & i23 & "+" & a24 & "*" & i24 & "+" & a25 & "*" & i25 & "+" & a26 & "*" & i26 & "+" & a27 & "*" & i27 & "+" & a28 & "*" & i28 & "+" & a29 & "*" & i29 & "=" & aa1
        bb = Replace(bb, "+0*0", "")
        bb = Replace(bb, "*1", "")
        bb = Replace(bb, Val(Text1(0)) & "*0+", "")
        For i = 0 To 29
            bb = Replace(bb, "+" & Val(Text1(i)) & "*0", "")
        Next
        Text1(30) = bb
        Exit Sub
    End If
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next

MsgBox "没找到"

End Sub

汗...好夸张

最初由 menglv 发布
高手，小弟用vb没用剪枝30个数就花去将近2分钟。你的程序很快，厉害！
这是小弟的代码，相当愚昧。
Private Sub Command1_Click()
Dim i0 As Double
Dim i1 As Double
........

能把VB用成这样，你是第一人了。

RoBa的代码写的真是规范,呵呵,是标准的格式了!
  祝你ACM成功啊~!

4楼的仁兄，可否将你的算法思路讲一下，我只懂vb，所以你写的c，我看得不是很懂，或者有谁能将其转化为basic程序，谢谢。顺便写出所有解的程序出来。

int cmp(const void *a,const void *b)
{
  int *tmpa,*tmpb;
  tmpa = (int*)a;
  tmpb = (int*)b;
  return *tmpa - *tmpb;
}
如果tmpa是很大的正数而tmpb是大负数，或者相反，这个计算结果就可能溢出，
并由此产生不正确的结果。是不是这样更安全哪
int cmp(const void *a,const void *b)
{
  int tmpa,tmpb;
  tmpa = *(int*)a;
  tmpb = *(int*)b;
  if(tmpa < tmpb)
          return -1;
  else if(tmpa == tmpb)
          return 0;
  else
    return 1;  
}

最初由 menglv 发布
4楼的仁兄，可否将你的算法思路讲一下，我只懂vb，所以你写的c，我看得不是很懂，或者有谁能将其转化为basic程序，谢谢。顺便写出所有解的程序出来。

思路应该比较清楚的吧,主要就是一个递归的solve()函数,第一个参数是开始的元素下标,第二个参数剩下的数的和应当是多少,当第二个参数为0时表示找到了一个解.

要求所有解把solve函数里:
if (solved) return;      //如果找到解则直接返回
这一句去掉即可.

to hejiwen:

试了一下的确有这个问题,为了省事常这么写,以前没注意过,万分感谢....

如果我没有记错!IPB的NO.2中就用到了背包算法!好像就是你介绍的算法!呵呵!我是穷举解决的!希望你找到好的方法!

能否把你的程式完善一下，求出满足条件的所有解？

最初由 menglv 发布
能否把你的程式完善一下，求出满足条件的所有解？

??
我在11楼说的方法不行??

可以了，很好的算法！
能否先估等式是由几位数组成，再在这几位里找，这样可能会更快？
比如：1 2 3 4 5 total=6
6>5 所以至少有两个数组成
6=1+2+3 所以三位数只有一种，其他只需在两个数里找。

To5楼的:
为什么不一串地定义呢,
如Dim a1,a2,a3...... as Double

Dim a1,a2,a3...... as Double
这样是很不规范的写法！
其实你这样写只是定义了最后一个变量！！！
没有定义变量，编译后运行的速度会很慢！！！

为的只是增加编译后运行的速度，不定义会很慢的！
不好意思。
前面 Dim i1 as Double.......Dim i29 as Double
应为 Dim i1 as Long  .......Dim i29 as Long
Double是双精度，为了支持小数。
当然我的方法只是很笨的一个方法，即所有的组合都用上了，效率很低！！！

menglv你的穷举如果在开始对数字排序。
dim total as double
total = 0
然后每层循环中
total=total+循环变量*该层数字
if total>N then exit for
速度会有极大的提高

另外最快的算法还是回溯， 不过还是递归更容易理解和编写了。

楞是来学习了

速度应该不会有极大的提高吧？？？
你有测试吗？？？
我这种方法对数字排序也没用！！！
因为它不能更早的退出！！！
有更快的程式可以贴出来。