探讨一道经典的算法问题，参与者有分！

Question

有这样一道算法问题：
  已知参数:a1,a2,a3,a4,......a20；（所给参数为整数）
           a1+a2+a3+a4+a5+.....a20=100；
  所求参数：x1,x2,x3,x4,......x20；
  限制条件：n<y<m (注：m,n为已知条件)
  计算公式： y=a1x1+a2x2+a3x3+a4x4+.....+a20x20；
 
我的计算方式很原始：
  for i:=1 to 100 do
    begin
      for j:=1 to 100-i do
        begin
         ............
         ............
          if n<a1x1+a2x2+a3x3+......a20x20<m and a1+a2+a3+....a20=100 then
             begin
             .............
             end;
        end;
    end;
   使用这种算法，普通的机子无法运行，因为循环次数太多
   欢迎大家畅所欲言！

Answer 1

似乎就是一个简单的搜索穷举
不过问题有一点你没有说清楚: 已知参数:a1,a2,a3,a4,......a20；（所给参数为整数）
           a1+a2+a3+a4+a5+.....a20=100；a1 .....a20 都是已知数吗?

Answer 2

你也是的，这种问题照你的说法，就变成了数学上的问题了，但是计算机是用来解决实际问题的。
你能告我解有什么限制条件吗？假如是up的话，解将有很多，这将加大时间复杂度，可能解不出来。
最起码应该有个条件限制xi，象整数，或者大于零之类的。

Answer 3

a1,a2,a3,a4,......a20
都是正整数吗
x1,x2,x3,x4,......x20
是要求为正整数？整数？实数?

Answer 4

请各位朋友注意：
所给的参数为已知：即：a1，a2,a3....a20；
所求的数：x1,x2,x3.....x20也为整数。（注在；解可能有多个）
若那位朋友还有什么疑问，可再提出！

Answer 5

有点意思，有点难度：
   给你点提示：a1,a2,a3,a4,......a20：Integer;               a1+a2+a3+a4+a5+.....a20=100；    所以任何一个a[i] 都可以表示为：a[i]：=5 + X[i]  -5=< X[i] <= 95 
 
........................好象条件不够！
呵呵！
抛砖引玉！

Answer 6

>>请各位朋友注意：
所给的参数为已知：即：a1，a2,a3....a20；
所求的数：x1,x2,x3.....x20也为整数。（注在；解可能有多个）
若那位朋友还有什么疑问，可再提出！
_______________________________
如果条件就这样的话，解也许太简单了。
我的办法是： 先求y,比如y=(n+m)/2，然后使x1,x2,x3.....x19=1,2,3...19,最后解一元一次方程1a1+2a2+3a3+...+19a19+xa20=y找到x使不就行了。

Answer 7

不是这样的， 你可以求出所有的Ai来，这样对应一种a 的可能值，就有20种解，
x的解可能是：
        0，0，0，0，0，0，0，..........y/Ai;
对应一种这样的解，就用400种可能解，当然，Ai 的所有可能是可以算出来的， 但是xi就不一定了，如果是所有的正整数，才有可能。
你学过线形代数的话，你可以知道它的特解是上面的表达式，他的两个秩相等，等于1，但它只有一个方程，所以解是无穷的。
你可以将原原本本的题写一下。

Answer 8

fbnic()分析的极是！如果可以是负的，穷举不完喽。。 ：）
如果是全正，深度优先穷举就好了。至于边界条件，你可以设 ，你可以用已确定的数，来确定为确定的数的范围。至于优化的方法慢慢考虑吧，差不多了

Answer 9

That's so funny!m,n告诉具体值了么?
y=a1x1+a2x2+a3x3+a4x4+.....+a20x20中是
y=a(i)*x(i)么?
你用的冒泡算法能写完整么?

Answer 10

fbnic()所说的也是一种解决问题的方法，但我们毕竟要把这种思想用计算机来表达，如果用计算机语言来表大，是不是有点难度,各位可以继续探讨下去！
我说的这是一个实际问题的模型，是一种配棉方案同时，我在把这道题重新整理一下；
有这样一道算法问题：
  已知参数:a1,a2,a3,a4,......a20:float;
  所求参数 x1,x2,x3,x4,......x20:integer;
          x1+x2+x3+x4+x5+.....x20=100；
         and  x1,x2,x3,....x20>0;
  限制条件：n<y<m   //m,n为已知条件
  计算公式： y=a1x1+a2x2+a3x3+a4x4+.....+a20x20；

Answer 11

我来给个思路吧。
下面是我用C++写的一段实现，用到了堆栈，和递归。
//-----header file Valuesum.H --- 
//加权和
#ifndef VALUESUM_H_ZERO
#define VALUESUM_ZERO
//使用栈
#include "stack.h"class TValueSum;class TItemData 
{
friend class TValueSum;
public:
int Index;
int Value;
TItemData(int AIndex,int AValue);
};typedef TItemData  *PITEMDATA;class TValueSum
{
Stack<PITEMDATA> stData;
int pWeights[1024];//加权值
int nCount;
public:
void PopStack();
void Run();
protected:
void Func_Run(int Y,int M,int N);
void OutputResult();
void PushStack(int AIndex,int AValue);
};
#endif // VALUESUM_ZERO//------CPP file --- 
//加权和的实现
#include <iostream.h>
#include "Valuesum.H"
/* TItemData */
TItemData::TItemData(int AIndex,int AValue)
{
Index = AIndex;
Value = AValue;
}/* TValueSum */
//以递归的形式实现问题的求解
void TValueSum::Func_Run(int Y,int M, int N)
//Y:加权和　　M:和 N:项数
{
   if ((Y<0) || (M<0) ||(N<2))
   {
   return;
   };
   if (N == 2)
   {
if (pWeights[1]==pWeights[0])
{
if (pWeights[1]*M-Y) 
{
PushStack(2,M);
PushStack(1,0);
OutputResult();
PopStack();
PopStack();
}
return;
} //Oupput Result;
double X1,X2;
//X1 = (M*A2-Y)/(A2-A1)
X1=(pWeights[1]*M-Y) / (pWeights[1]-pWeights[0]);
//X2 = (Y-A1*M)/(A2-A1)
X2=(Y-pWeights[0]*M) / (pWeights[1]-pWeights[0]);
if ( (X1==int(X1)) && (X2==int(X2)) 
&& (X1>=0) &&(X2>=0)) 
{
PushStack(2,int(X2));
PushStack(1,int(X1));
OutputResult();
PopStack();
PopStack();
}
return;
   }   for (int i =0;i<M;i++) 
   {
//Push Stack
PushStack(N,i);
Func_Run(Y-pWeights[N-1]*i,M-i,N-1);
//Pop Stack
PopStack();
   }
}void TValueSum::PushStack(int AIndex, int AValue)
{
PITEMDATA pData = new TItemData(AIndex,AValue);
stData.Push(pData);
}void TValueSum::PopStack()
{
PITEMDATA pData;
pData = stData.Pop();
delete pData;
}void TValueSum::OutputResult()
{
Stack<PITEMDATA> stTemp;//临时堆栈
PITEMDATA pData;
while(!stData.IsEmpty()) 
{
pData = stData.Pop();
cout <<"X["<<pData->Index<<"]:"<<pData->Value<<" ";
stTemp.Push(pData);
};
cout <<endl; //将临时堆栈返回数据堆栈
while(!stTemp.IsEmpty()) 
{
pData = stTemp.Pop();
stData.Push(pData);
};
nCount++;
}void TValueSum::Run()
{
int nNumber,yMax,nSum ;//yMin,
int i;
nNumber  = 0;
while ((nNumber <= 0) || (nNumber>1024))
{
cout<<"please Input Number of Value:"<<endl;
cin >>nNumber;
}
cout<<"please Input Summer of Value:"<<endl;
cin >>nSum;
cout<<"please Input the weights total "<<nNumber<<endl;
for (i =0;i<nNumber;i++)
{
cin >>pWeights[i];
}
cout<<"please Input  Weight Sumer of Value:"<<endl;
cin >>yMax;
nCount = 0;
Func_Run(yMax,nSum,nNumber);
//cout<<"please Input Max ,Min Weight Sumer of Value:"<<endl;
//cin >>yMax>>yMin;
//for (i=yMin;i<yMax;i++) 
//{
// Func_Run(i,nSum,nNumber);
//}
cout<<"Total Resoult :" << nCount<<endl;
}

Answer 12

以成员函数Func_Run(int Y,int M, int N)来实现对问题的求解
其中 Y:加权和： 即 = a[1]*X[1] + ...+a[N]*X[N]
 　　M:和     = X[1] + ...+ X[N]
    N:项数   
主要就是一个递归。
// pWeights为输入的加权参数数组
for (int i =0;i<M;i++) 
   {
//Push Stack
PushStack(N,i);
Func_Run(Y-pWeights[N-1]*i,M-i,N-1);//实现一层递归
//Pop Stack
PopStack();
   }
再不懂，我就没办法了。
算法的效率不是很好。
谁有更好的，热切期待中