求助高手，一个类似找钱（coin change）的算法
有那么一个问题，有一组数字和一个数字
一组数字 5，10，15，25，50
一个数字 215
问题是215能不能由 这一组数字中任意一些数字组成。
比如215 = 8个25 + 1个15 组成
265 = 8个25 1个50 1个15组成
现在的问题是，只要找到任意一个组成了就可以返回。。不用管到底有多少中组成， 如果找不到
例如299， 最后结果就是不能组成。。
我用的办法是递归+全局判断。。问题出现了。。当一组数字中个数大于4个。。数字大于2000的时候速度一下子变慢，特别是找不到组成的时候。。我看了下一共循环了几千外次。。
比如 5，10，15，25，50 和 2011的时候，，运算了几十秒。。问问大侠有没有快速点的算法。。如果没有更好的算发能不能+一些判断提高速度。。
那一组数字的个数可能是4-10个 （只要设定了就是确定的，基本不会修改）。。一个数字1-100000 （是随机的）。。。
1. 提高速度的判断我就想到了求这几个数字的公约数。。看是不是能被2011整除。。如果不是的话就直接不能组成了
static bool res = false;
static int count = 0;
static void findAllCombinationsRecursive(List<int> notes, int startIx, int remainingTarget)
{
for (int i = startIx; i < notes.Count && !res; i++)
{
count++;
int temp = remainingTarget - notes[i];
if (temp < 0)
{
break;
}
if (temp == 0)
{
// reached the answer hence quit from the loop
res = true;
}
else
{
// target not reached, try the solution recursively with the
// current denomination as the start point.
findAllCombinationsRecursive(notes, i, temp);
}
}
}
[解决办法]
背包问题
[解决办法]
判断的时候所有是其他数字整数倍（大于1）的数可以直接去掉，大概就没几个数字了，像你的例子就只剩下5了
[解决办法]
顶楼上，用“一个数”分别除以“一组数”中的每个元素，得出该元素最多可能的个数，然后剩下的就是完全背包且恰好装满的问题了。
[解决办法]
5x + 10y + 15u + 25v + 50t = p，左边可以被5整除，这要求右边也可以倍5整除，2011显然不是5的倍数，无解。你搜一次啊不定方程的求解，应该有帮助的。
整数：a,b,x,y,p；ax + by = p;c表示a,b,的公约数，只有p可以被c整除，才能有解
[解决办法]
楼主的问题可以这样描述:
给定集合A={a1,a2,...,an}是数字集合,比如 A={5，10，15，25，50},及C是那个目标整数,比如 C=215,求一个非负整数集合P={p1,p2,...,pn},使得 p1*a1+p2*a2+...+pn*an=C.
解:该问题是一个变相的"子集和"问题.
定义布尔二维数组 F[i,j] 如下:
F[i,j]=True 当且仅当存在 {a1,a2,...,ai} 的子集B,使得B中各元素能"拼出"j.
由 F[i,j] 的定义,我们有如下递推式:
F[i,0]=True,i=1,2,...,n. 因为,对于C=0而言,我们可把所有系数取为 0.
F[1,j]=True 当且仅当 j 能整除x1. j=1,2,...,C.
F[i,j]=F[i-1,j] 当 ai>j
=F[i-1,j] OR F[i,j-ai] 当ai<=j
我们可用 O(C*n) 时间算出 F.
F[n,C] 若为 True ,表示可以拼出C,否则不行.
若能拼出C,由下面算法得出各系数p1,p2,...pn:
for (i=1;i<=n;i++) p[i]=0; // 开始时,各系数为 0
for (j=C,i=n;j>0 && i>1;)
if (F[i-1,j]) // 不用 xi 也可以
{
i--;
}
else // 不用 xi 不行
{
p[i]++;
j-=ai;
}
p[1]+=j/a1; // 把最后的零头加到 p1 头上
输出 p1,p2,...,pn
计算 p1,p2,...,pn 耗时 O(C*n)
本人在自己的本本上实现了上面算法,并把楼主给出的实例输入到算法中,实际耗时不到 1ms.
