请教一个算法！急！ (200分)

大哥，不要着急。我已经有思路了：
每次取一种颜色，根据这种颜色之后的“重量覆盖”情况确定哪几个重量必须取。依次类推...

我的算法如下：
前提：排除不被取的颜色的球
1。排除被取完的颜色的球
1。优先取包含颜色数最少的那种重量的小球
2。如果该种重量包含的颜色不只一种，则取包含重量数最少的颜色
3。确定了重量和颜色之后取一个，排除该种重量
4。重复。
所有重量取完之后，剩下的球按颜色随意取
我觉得我的算法应该没什么错了，但苦于无法证明，而且太复杂了，还要从数据库中取，
头大。
算法应该不只一种啊！

如果能证明我错，也是好的

>>太复杂了，还要从数据库中取
怎么在数据库上吊死了？你完全可以将所有元素的信息读入内存（只要小于10^6，都是可以接受的），
然后像我在上面那样列表，进行递归穷举，若在某一层失败则返回上一层...在获得一个可行方案之后，
最后才正式的从数据库中取出来。要是真的每次试探都要进行数据库读写的话，那谁受得了？
>>优先取包含颜色数最少的那种重量的小球
——经验主义，没有任何根据。
球 的 个 数
重量 Color1 Color2 Color3
1 1 0 0
2 3 2 1
3 0 1 3
4 2 2 4
要取的球数 2 1 3
我的思路是：分析每个重量可以由哪几种颜色的小球来分担，每次将一种颜色的小球取完。
以上面的表为例，我们可以发现，重量为1的小球只有Color1一种，因此Color1中重量为1的小球
必须被选中，于是题目简化为：
重量 Color1 Color2 Color3
2 3 2 1
3 0 1 3
4 2 2 4
要取的球数 1 1 3 另外附加一个 Color1，重量为1的球。
然后研究Color1之后其它颜色的重量覆盖情况，发现每种重量都被覆盖到了，Color1可以进行没有
限制的递归组合运算（即随机取一个重量为2的，或者一个重量为4的）。
如果取了重量为2的，题目进一步简化为：
重量 Color2 Color3
2 2 1 ——此重量已被前面的颜色覆盖，可取可不取
3 1 3 ——尚未覆盖
4 2 4 ——同上
要取的球数 1 3
如此递归取球...

你说的：
我们可以发现，重量为1的小球只有Color1一种，因此Color1中重量为1的小球
必须比选中，
和我说的第二条是一样的。
你的算法我不太明白，第一步很简单（你举的情况简单），第二步怎么办？又能取出哪个球呢？
我当然知道要将数据一次性读入内存，可是用什么数据结构来存放呢？我想应该是数组，
那样操作不是很烦吗？

哦，我刚刚回复的时候，你还没贴全，现在明白了。
你的算法如果碰到那种部分覆盖的情况，就有可能取错，这样就得回溯了，
当数据量大的时候，你可想过回溯的工作量？
我的qq：57376684，欢迎讨论

如果情况如下：
c1 c2 c3
1 3 3 0
2 3 1 0
3 3 1 4
4 2 0 1
取：2 2 3
按你的算法怎么取？

既然每种重量一定都要有，那就把球分成w组，每组一个依次取过去（随机取，不定颜色）
但是颜色够的就不能再取了，这样循环到够了为止

sfen：那到后来，有的颜色取不到了怎么办？

大哥，我这不正在一边想一边写嘛。
你所说的情况我已经想到了，只不过实现起来比较麻烦。用我现在的算法也可以实现，只不过
要用到回溯，可能做一些无用功。
另：俺还没有QQ ——大家没有晕倒吧

我已经很感谢你了！

最初版完成！
TBuffer类的代码请看 http://www.delphibbs.com/delphibbs/dispq.asp?lid=968511
功能：穷举所有可能的组合方案
type
IAA=array of array of Integer;
function GetBallOnWeight(ColorNum,WeightNum:Integer;Balls:IAA;
GetNum:array of Integer):Integer;
var
ColorBallNum, //指定的颜色已取得的球数
WeightBallNum:array of Integer;
//指定的重量已取得的球数
Solution, //解决方案数组，结构同Balls --它和Balls始终保持互补关系，此消彼涨
BallPos:IAA;
//记录球的位置，用于穷举
BindBallStack:TStack;
WeightMaps,
WieghtColorNumArray:IAA;
//重量覆盖表 --针对映射之后的WeightMap
Buffer:TBuffer;
procedure UseBall(Ci,Wi:Integer);
begin
Dec(Balls[Ci][Wi]);
Inc(Solution[Ci][Wi]);
BallPos[Ci][WeightBallNum[Wi]]:=Wi;
Inc(WeightBallNum[Wi]);
Inc(ColorBallNum[Ci]);
end;
procedure UnuseBall(Ci,Wi:Integer);
begin
Inc(Balls[Ci][Wi]);
Dec(Solution[Ci][Wi]);
Dec(WeightBallNum[Wi]);
Dec(ColorBallNum[Ci]);
end;
procedure GetBallLevel(Level:Integer;WeightMapNum:Integer);
var
WeightMap,
WeightCover:array of Integer;
BindCount:Integer;
//在此层中绑定的球数
function ValidCheck:Boolean;
//合法性检查
var
vi,vj,vs:Integer;
begin
Result:=false;
WeightCover:=@WieghtColorNumArray[Level][0];
FillChar(WeightCover[0],WeightNum*SizeOf(Integer),0);
for vi:=0 to WeightMapNum-1do
begin
vs:=0;
for vj:=Level to ColorNum-1do
if Balls[vj][WeightMap[vi]]>0 then
Inc(vs);
if (vs=0) and (WeightBallNum[WeightMap[vi]]=0) then
exit;
WeightCover[vi]:=vs;
end;
Result:=true;
end;
function TrimWeight:Boolean;
var
i,j,MapW,k,OldMapNum:Integer;
NewWeightMap:array of Integer;
b:Boolean;
begin
Result:=true;
NewWeightMap:=@WeightMaps[Level+1][0];
k:=0;
OldMapNum:=WeightMapNum;
for i:=0 to OldMapNum-1do
begin
MapW:=WeightMap;
b:=true;
if (WeightCover=1) and (WeightBallNum[MapW]=0) then
begin
//发现了一个必须填补的重量空缺
Result:=false;
for j:=Level to ColorNum-1do
if Balls[j][MapW]>0 then
begin
UseBall(j,MapW);
BindBallStack.Push(Pointer((j shl 16) or MapW));
//高位Color,低位重量
Inc(BindCount);
if Balls[j][MapW]=0 then
b:=false;
Result:=true;
break;
end;
if not Result then
exit;
end;
if b then
begin
NewWeightMap[k]:=WeightMap;
Inc(k);
end;
end;
WeightMap:=@NewWeightMap[0];
WeightMapNum:=k;
end;
procedure UnbindAll;
//退回所有在这一层中使用的球
var
i,m:Integer;
begin
for i:=0 to BindCount-1do
begin
m:=Integer(BindBallStack.Pop);
UnuseBall(m shr 16,m and $0000FFFF);
end;
end;
procedure PN(M:Integer;StartFromZero:Boolean=false);
var //计算第Level种颜色的球中，第M个的可能位置
i,s,w:Integer;
function WeightInMap(Wi:Integer):Integer;
begin
//在重量映射表中寻找重量Wi所处的位置
Result:=0;
while WeightMap[Result]<>Wido
Inc(Result);
end;
begin
if M=GetNum[Level] then
begin
GetBallLevel(Level+1,WeightMapNum);
exit;
end;
if StartFromZero then
s:=0
else
s:=WeightInMap(BallPos[Level][M-1]);
//起始重量不能比前面的相同颜色的球小
for i:=s to WeightMapNum-1do
begin
w:=WeightMap;
if Balls[Level][w]>0 then
begin
UseBall(Level,w);
PN(M+1);
UnuseBall(Level,w);
end;
end;
end;
procedure OutputResult;
var
i,j:Integer;
mstr:String;
begin
mstr:='';
for i:=0 to WeightNum-1do
begin
for j:=0 to ColorNum-1do
mstr:=mstr+IntToStr(Solution[j])+#9;
mstr:=mstr+#13#10;
end;
mstr:=mstr+#13#10;
Buffer.WriteBuf(@mstr[1],Length(mstr));
end;
begin
WeightMap:=@WeightMaps[Level][0];
if not ValidCheck then
exit;
if Level=ColorNum then
begin
Inc(Result);
OutputResult;
exit;
end;
BindCount:=0;
if not TrimWeight then
begin
UnbindAll;
exit;
end;
PN(ColorBallNum[Level],true);
UnbindAll;
end;
var
i,j,s:Integer;
begin
Result:=0;
SetLength(ColorBallNum,ColorNum);
FillChar(ColorBallNum[0],ColorNum*SizeOf(Integer),0);
//初始化颜色-球数表
SetLength(WeightBallNum,WeightNum);
FillChar(WeightBallNum[0],WeightNum*SizeOf(Integer),0);
//初始化重量-球数表
SetLength(Solution,ColorNum);
for i:=0 to ColorNum-1do
//初始化解决方案表
begin
SetLength(Solution,WeightNum);
FillChar(Solution[0],WeightNum*SizeOf(Integer),0);
end;
SetLength(WeightMaps,ColorNum+1);
for i:=0 to ColorNumdo
//一次性分配重量映射表空间
SetLength(WeightMaps,WeightNum);
for i:=0 to WeightNum-1do
//初始化最底层的重量映射表
WeightMaps[0]:=i;
SetLength(WieghtColorNumArray,ColorNum+1);
for i:=0 to ColorNumdo
//一次性分配重量覆盖表空间
SetLength(WieghtColorNumArray,WeightNum);
SetLength(BallPos,ColorNum);
for i:=0 to ColorNum-1do
begin
s:=0;
for j:=0 to WeightNum-1do
Inc(s,Balls[j]);
SetLength(BallPos,s);
end;
Buffer:=TBuffer.Create;
BindBallStack:=TStack.Create;
GetBallLevel(0,WeightNum);
BindBallStack.Free;
Form1.Memo1.Text:=Buffer.AsString;
Buffer.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
Balls:IAA;
GetNum:array of Integer;
i,j,CNum,WNum:Integer;
begin
CNum:=SpinEdit1.Value;
//颜色数，这里为3
WNum:=SpinEdit2.Value;
//重量数，这里为4
SetLength(Balls,CNUm);
for i:=0 to CNum-1do
SetLength(Balls,WNum);
SetLength(GetNum,CNum);
with StringGrid1do
begin
for i:=0 to CNum-1do
for j:=0 to WNum-1do
Balls[j]:=StrToIntDef(Cells[i+1,j+1],0);
for i:=0 to CNum-1do
GetNum:=StrToIntDef(Cells[i+1,WNum+1],0);
end;
Caption:=IntToStr(GetBallOnWeight(CNum,WNum,Balls,GetNum));
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
DrawGridTitle;
with StringGrid1do
begin
Cells[1,1]:='1';
Cells[2,1]:='0';
Cells[3,1]:='0';
Cells[1,2]:='2';
Cells[2,2]:='3';
Cells[3,2]:='1';
Cells[1,3]:='0';
Cells[2,3]:='2';
Cells[3,3]:='4';
Cells[1,4]:='2';
Cells[2,4]:='0';
Cells[3,4]:='1';
Cells[1,5]:='2';
Cells[2,5]:='1';
Cells[3,5]:='3';
end;
end;

procedure TForm1.DrawGridTitle;
var
i:Integer;
begin
with StringGrid1do
begin
for i:=1 to ColCount-1do
Cells[i,0]:='C'+IntToStr(i);
for i:=1 to RowCount-2do
Cells[0,i]:='W'+IntToStr(i);
Cells[0,RowCount-1]:='Num';
end;
end;

Result: (共10个)
1 0 0
1 1 1
0 0 1
0 0 1
1 0 0
1 1 0
0 0 2
0 0 1
1 0 0
1 0 1
0 1 1
0 0 1
1 0 0
1 0 0
0 1 2
0 0 1
1 0 0
0 1 1
0 0 2
1 0 0
1 0 0
0 1 1
0 0 1
1 0 1
1 0 0
0 1 0
0 0 3
1 0 0
1 0 0
0 1 0
0 0 2
1 0 1
1 0 0
0 0 1
0 1 2
1 0 0
1 0 0
0 0 1
0 1 1
1 0 1

通过增强 function ValidCheck:Boolean;
//合法性检查 过程的判断能力，可以做到将回溯
控制在一层以内。

谢谢！
我想能不能通过矩阵变换求解：
c1 c2 c3 c4
w1 5 2 0 0 ---->
w2 0 4 4 4
w3 2 2 2 6
c2 c4 c3 c1
--->w1 1 0 0 0
w2 0 1 0 0
w3 0 0 1 0
w4 0 0 0 1

呵呵，线性代数基本上忘完了。
我认为这个问题属于排列组合问题——有很多个合理解，穷举是必须的，并不是线性代数所擅长的
方程求解问题。如果可能的话，请您给出下面问题的线性代数的解以及解法（思路）：
c1
w1 2
w2 4
w3 6
Num 5
另外问一句：对我上面给出的算法，您有什么不满意吗？ （如果认为速度慢、没有必要完全穷举，
您可以修改 procedure PN 中的 for i:=s to WeightMapNum-1do
循环，随机取重量呀）

：），我不是不满意！我只是在想还有没有别的方法而已
你说的那个矩阵
就是：
c1
w1 1
w2 1
w3 1
忘了说明白我的想法了！我想分成两步取：
首先每个重量各取一个
然后剩下的就可以按颜色随便取了

噢！是我不对！

对不起！！！
有一点我写错了，就是并不能保证所有的重量都被取到，只能要求取到尽可能多的重量种类！

还是creation-zy的算法吧

creation-zy的时间和精力绝对让人钦佩，呵呵
应该还在读书吧

谢谢creation-zy