几天没休息好，头昏脑胀，求个算法
几天没休息好，头昏脑胀，求个算法
已知：
一个大数V,很大
数字A
数字B
数字C
数字D
数字...
A、B、C、D、...这些数字远小于V,而且他们的和(A+B+C+D+...)也远小于V
求满足如下条件：
A1*x1+B1*x2+C1*x3+D1*x4+...=V
A1<=A
B1<=B
C1<=C
D1<=D
并且x1>x2>x3>x4
的所有
A1-x1
B1-x2
C1-x3
D1-x4
的组合
--------------------------------------------
例如
V=654321
A=54
B=257
C=19
D=360
求满足如下条件
A1*x1+B1*x2+C1*x3+D1*x4=V
A1<=A
B1<=B
C1<=C
D1<=D
并且x1>x2>x3>x4
的所有
A1-x1
B1-x2
C1-x3
D1-x4
的组合
看到算法头疼
[解决办法]
我数学老师被程序员给绑架了 所以帮不上你 但是帮顶！！
[解决办法]
[解决办法]
看了一会，感觉可以帮你的只有顶一下了...
[解决办法]
單單這些條件還不夠吧，數字的正負或者數字為整型還是浮點型都沒有明確說明。
[解决办法]
我表示看的头疼。。。。
[解决办法]
真不好搞，全都是未知的数，而且还要是4个数才是一个组合一个解，真有这样的算法吗?
Mark下先
[解决办法]
坐 等 大 牛
[解决办法]
可能性太多了，即使只考虑A1=A，B1=B，C1=C，D1=D这一种情况，在x1>x2>x3>x4，且x4>0的情况下，程序已算到7万中组合了， 目前54*9983+257*333+19*1542+360*1
可以看出x4还停留在1，这样看来，组合起码1千万种
[解决办法]
private static int iGroupCnt = 0;
private static int[] arrSum;
private static int[] arrFloorSum;
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
int[] arrABC = new int[] { 54, 257, 19, 360 };
int V = 654321;
//存放x1x2x3x4
int[] arrX = new int[arrABC.Length];
//为了处理x1>x2>x3>x4的限定条件，加的2个数组
arrSum = new int[arrABC.Length];
arrFloorSum = new int[arrABC.Length];
for (int i = 0; i < arrABC.Length; i++)
{
if (i > 0)
{
arrSum[i] = arrSum[i - 1] + arrABC[i];
arrFloorSum[i] = arrFloorSum[i - 1] + arrSum[i - 1];
}
else
{
arrSum[i] = arrABC[i];
}
}
//当前处理的数的序号，右边的x值最小，从右边的数开始
//序号
int iCurIndex = arrABC.Length - 1;
//值
int iCur = arrABC[iCurIndex];
//组合次数
iGroupCnt = 0;
//遍历函数
IterateFun(arrABC, iCurIndex, arrX, V);
////如果考虑A1<=A，B1<=B，C1<=C，D1<=D的情况
////再外面加循环就行了，我给个嵌套的写法，你可以改成递归的方式，以适应ABC个数不确定
//int[] arrABC2 = new int[arrABC.Length];
//for (int i = 0; i < arrABC[0] + 1; i++)
//{
// arrABC2[0] = i;
// for (int j = 0; j < arrABC[1] + 1; j++)
// {
// arrABC2[1] = j;
// for (int m = 0; m < arrABC[2] + 1; m++)
// {
// arrABC2[2] = m;
// for (int n = 0; n < arrABC[3] + 1; n++)
// {
// arrABC2[3] = n;
// IterateFun(arrABC2, iCurIndex, arrX, V);
// }
// }
// }
//}
sw.Stop();
Console.WriteLine("组合数：" + iGroupCnt);
Console.WriteLine("花费:"+sw.ElapsedMilliseconds+"毫秒");
Console.ReadLine();
}
/// <summary>
/// 递归函数
/// </summary>
/// <param name="arrABC">ABC数组</param>
/// <param name="iCurIndex">当前序号</param>
/// <param name="arrX">x1x2数组</param>
/// <param name="VRemain">V剩余值</param>
private static void IterateFun(int[] arrABC, int iCurIndex, int[] arrX, int VRemain)
{
//当前序号对应的值
int iCur = arrABC[iCurIndex];
if (iCurIndex < 1)
{
//如果还剩下A没有计算，直接判断能否整除
int iRemainder = VRemain % iCur;
if (iRemainder == 0 )
{
int iQuotient = VRemain / iCur;
arrX[iCurIndex] = iQuotient;
//输出到屏幕中
//string s = "";
//for (int i = 0; i < arrIn.Length; i++)
//{
// s += string.Format("{0}*{1}+", arrIn[i], arrLoop[i]);
//}
//s = s.TrimEnd('+');
//Console.WriteLine(s);
iGroupCnt++;
}
}
else
{
//如果x1x2不考虑为0的情况，请将此处改为1
int iMinX = 0;
//前N项ABC之和
int iSum = arrSum[iCurIndex];
//因为x1>x2>x3>x4的限定，所以当计算x4时要减去(3x1+2x2+x3)
int iFloorSum = arrFloorSum[iCurIndex];
int iVRemainTmp = VRemain - iFloorSum;
//考虑x1>x2>x3>x4限定后，X的最大取值，包括此最大值
int iMaxX = iVRemainTmp / iSum;
//当前X最小值不能比后面的X小
if (iCur < arrX.Length - 1)
{
iMinX = arrX[iCurIndex + 1] + 1;
}
for (int i = iMinX; i < iMaxX + 1; i++)
{
arrX[iCurIndex] = i;
//遍历
IterateFun(arrABC, iCurIndex - 1, arrX, VRemain - i * iCur);
}
}
}
