*A+*B+*C+*D的分解问题

Question

有一个问请你帮忙解决，问题是：*A+*B+*C+*D,其中*代表的是0..N的正整数。　
可分解项有
(1)A+B+C+D 　　　　　　　　  28元
(2)A+B+C或A+B+D 　　　　　　 23元 
(3)B+C+D或A+C+D 　　　　　　 19元
(4)A+B,A+C,A+D,B+C,B+D,C+D,　15元1）如2A+2B+C+D分解成
　一种方法：A+B+C+D、A+B=28元+15元=43元
　二种方法：A+B+C、A+B+D=23元+23元=46元
　三种方法：A+B、A+B、C+D=15元+15元+15元=45元
　当然我先第一种方法更便宜43元最小。
2）如3A+3A+0C+0D分解成
　　A+B、A+B、A+B=45元。 请问有谁能帮我设计这个算法，我给他几百分，另还有给分。急！急！

Answer 1

2A+2B+C+D = (B+C+D)+(A+C+D)+(A+B)-(C+D) 其中（A+B）= （C+D）
根据(3)B+C+D或A+C+D 　　　　　　 19元所以2A+2B+C+D = (B+C+D)+(A+C+D)= 38元，呵呵比你的少，帅哥~~~难道我随便分解？你的需求是不是没搞清楚？算法是很好写的，你的需求必须搞清楚。
如分解规则说清楚，我帮你算法，呵呵~~~~

Answer 2

gemouzhi(gemouzhi) 
：不是你哪种算法。2A+2B+C+D 是一个由
(1)A+B+C+D 　　　　　　　　  
(2)A+B+C或A+B+D 　　　　　　 
(3)B+C+D或A+C+D 　　　　　　 
(4)A+B,A+C,A+D,B+C,B+D,C+D
中的哪些组成，
明白！

Answer 3

无聊的问题
(B+C+D)+(A+C+D)+(A+B)-(C+D)  中的元素全是下面的啊：(1)A+B+C+D 　　　　　　　　  
(2)A+B+C或A+B+D 　　　　　　 
(3)B+C+D或A+C+D 　　　　　　 
(4)A+B,A+C,A+D,B+C,B+D,C+D你先把 组成和加法 分清楚再来，OK吗？明白！！！！！！！！！！！！

Answer 4

不对！不是加减。可以这么认为*A+*B+*C+*D　其中*代表（0..N）的正整数。

Answer 5

//为了提高效率,这个程序没有递归,它的效率是O(1),与输入的规模无关,可以在接近常数时间内求解
unit divide;interfaceuses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs,math, StdCtrls;const
   IA=1;IB=2;IAB=3;IC=4;IAC=5;IBC=6;IABC=7;ID=8;
   IAD=9;IBD=10;IABD=11;ICD=12;IACD=13;IBCD=14;IABCD=15;
   
type   TLetters=Array [1..15] of integer;
   //按下标的二进制保存划分过程中{A,B,C,D}的所有非空子集的个数,
  {1:A的个数
   10:B的个数
   11:AB的个数
   100:C的个数
   101:AC的个数
   110:BC的个数
   111:ABC的个数
   1000:D的个数
   1001:AD的个数
   1010:BD的个数
   1011:ABD的个数
   1100:CD的个数
   1101:ACD的个数
   1110:BCD的个数
   1111:ABCD的个数
  }
    TForm1 = class(TForm)
    Label1: TLabel;
    edtA: TEdit;
    Label3: TLabel;
    edtB: TEdit;
    Label4: TLabel;
    edtC: TEdit;
    Label5: TLabel;
    edtD: TEdit;
    memResul: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
    A:TLetters;
    function LetterToIndex(Letter:Char):integer; //从字母转换为下标
    function StrToIndex(str:String):Integer;    //从合法的字符串转换为下标
    function IndexToName(I:integer):string;//从下标转换成字符串
    function CanSolved:boolean; //是否可解
    procedure Search;
    procedure CreateTeam(TeamName:string;Num:integer); //由单个字母生成Num个TeamName编组
    procedure DetachTeam(TeamName:string;Num:integer); //解散Num个TeamName编组成为单字
    procedure ProceABX(X,Y:String);//处理多余的A,B,X;X=C或D;Y为可以在最优化过程中去掉的C或D
    procedure JoinC;
    procedure JoinD;
    procedure JoinA;
    procedure JoinB;
    function  OutPutStr:string;
  public
    { Public declarations }
  end;
  
var
  Form1: TForm1;implementation{$R *.dfm}
{ TForm1 }function TForm1.CanSolved: boolean;
begin
  result:=false;
  if A[1]+A[2]+A[4]<A[8] then exit;
  if A[1]+A[2]+A[8]<A[4] then exit;
  if A[1]+A[4]+A[8]<A[2] then exit;
  if A[2]+A[4]+A[8]>=A[1] then
     result:=true;
end;procedure TForm1.CreateTeam( TeamName: string; Num: integer);
var
  ITeam:integer;
  i:integer;
begin
  if Num<=0 then exit;
  ITeam:=StrToIndex(TeamName);
  Inc(A[ITeam],Num);
  for i:=1 to Length(TeamName) do
    Dec(A[LetterToIndex(TeamName[i])],Num);
end;procedure TForm1.DetachTeam(TeamName: string;
  Num: integer);
var
  ITeam:integer;
  i:integer;
begin
  if Num<=0 then exit;
  ITeam:=StrToIndex(TeamName);
  Dec(A[ITeam],Num);
  for i:=1 to Length(TeamName) do
    Inc(A[LetterToIndex(TeamName[i])],Num);
end;procedure TForm1.JoinA;
var
  ProNum:integer;
begin
  ProNum:=min(A[IA],A[IBC]);
  if ProNum>0 then
  begin
    DetachTeam('BC',ProNum);
    CreateTeam('ABC',ProNum);
  end;
  ProNum:=min(A[IA],A[IBD]);
  if ProNum>0 then
  begin
    DetachTeam('BD',ProNum);
    CreateTeam('ABD',ProNum);
  end;
  ProNum:=min(A[IA],A[IBCD]);
  if ProNum>0 then
  begin
    DetachTeam('BCD',ProNum);
    CreateTeam('ABCD',ProNum);
  end;
end;procedure TForm1.JoinB;
var
  ProNum:integer;
begin
  ProNum:=min(A[IB],A[IAC]);
  if ProNum>0 then
  begin
    DetachTeam('AC',ProNum);
    CreateTeam('ABC',ProNum);
  end;
  ProNum:=min(A[IB],A[IAD]);
  if ProNum>0 then
  begin
    DetachTeam('AD',ProNum);
    CreateTeam('ABD',ProNum);
  end;
  ProNum:=min(A[IC],A[IACD]);
  if ProNum>0 then
  begin
    DetachTeam('ACD',ProNum);
    CreateTeam('ABCD',ProNum);
  end;
end;procedure TForm1.JoinC;
var
  ProNum:integer;
begin
  ProNum:=min(A[IC],A[IAB]);
  if ProNum>0 then
  begin
    DetachTeam('AB',ProNum);
    CreateTeam('ABC',ProNum);
  end;
  ProNum:=min(A[IC],A[IABD]);
  if ProNum>0 then
  begin
    DetachTeam('ABD',ProNum);
    CreateTeam('ABCD',ProNum);
  end;
end;procedure TForm1.JoinD;
var
  ProNum:integer;
begin
  ProNum:=min(A[ID],A[IAB]);
  if ProNum>0 then
  begin
    DetachTeam('AB',ProNum);
    CreateTeam('ABD',ProNum);
  end;
  ProNum:=min(A[ID],A[IABC]);
  if ProNum>0 then
  begin
    DetachTeam('ABC',ProNum);
    CreateTeam('ABCD',ProNum);
  end;
end;function TForm1.LetterToIndex(Letter: Char): integer;
begin
  result:=1 shl (Ord(Letter)-Ord('A'));
end;procedure TForm1.ProceABX(X,Y: String);
var
  IX,IOther:integer;
  BestTeamNum,ANum,BNum:integer;
  MoreLetter:Char;//剩余较多的字母
begin
  IX:=StrToIndex(X);
  IOther:=StrToIndex(Y);
  BestTeamNum:=A[IOther];
  if A[IA]-A[IB]>A[IOther] then
     CreateTeam('ACD',A[IOther])
  else if A[IB]-A[IA]>A[IOther] then
     CreateTeam('BCD',A[IOther])
  else
  begin
    if A[IA]>A[IB] then
    begin
      ANum:=ceil((A[IA]-A[IB]+BestTeamNum)/2.0);
      BNum:=BestTeamNum-ANum;
      CreateTeam('ACD',ANum);
      CreateTeam('BCD',BNum);
      CreateTeam('A'+X,A[IX] div 2);
      CreateTeam('B'+X,A[IX]);
      CreateTeam('AB',Min(A[IA],A[IB]));
    end else
    begin
      BNum:=ceil((A[IB]-A[IA]+BestTeamNum)/2.0);
      ANum:=BestTeamNum-BNum;
      CreateTeam('ACD',ANum);
      CreateTeam('BCD',BNum);
      CreateTeam('B'+X,A[IX] div 2);
      CreateTeam('A'+X,A[IX]);
      CreateTeam('AB',Min(A[IA],A[IB]));
    end;
  end;
  if A[IA]>0 then JoinA;
  if A[IB]>0 then JoinB;
end;procedure TForm1.Search;
var
  BestTeamNum:integer; //最优组的个数(BCD+ACD)
  ACDNum,BCDNum:integer;
begin
  if not CanSolved() then
  begin
    ShowMessage('问题无解');
    exit;
  end;
  BestTeamNum:=Min(A[IA]+A[IB],Min(A[IC],A[ID])); //求得可购成最优组的个数
  if  (BestTeamNum = A[IA]+A[IB])  then //组成最优组合后,会剩下C和D
  begin
     CreateTeam('BCD',A[IB]);//把所有的B构成BCD组
     CreateTeam('ACD',A[IA]);//把所有的A构成ACD组
     //此时仅剩下C和D
     CreateTeam('CD',Min(A[IC],A[ID]));//CD两两组合
     //此时仅剩下C或D中的一种
     if A[IC]>0 then
        JoinC
     else
        JoinD;
  end else
  if  (BestTeamNum = A[IC]) then //组成最优组合后,会剩下A,B,D
    ProceABX('D','C')
  else //组成最优组合后,会剩下A,B,C
    ProceABX('C','D')
end;function TForm1.StrToIndex(str: String): Integer;
var
  i:integer;
begin
  result:=0;
  for i:=1 to Length(Str) do
   Result:=Result+LetterToIndex(Str[i]);
end;procedure TForm1.Button1Click(Sender: TObject);
var
  i:integer;
begin
  for i:=1 to 15 do
    A[i]:=0;
  A[1]:=strtoint(edtA.Text);
  A[2]:=strtoint(edtB.Text);
  A[4]:=strtoint(edtC.Text);
  A[8]:=strtoint(edtD.Text);
  Search;
  memResul.Lines.Text:=OutPutStr;
end;function TForm1.OutPutStr: string;
var
  i:integer;
begin
  result:='';
  for i:=1 to 15 do
    if A[i]>0 then
      result:=result+inttostr(A[i])+'*'+IndexToName(i)+'     ';
end;function TForm1.IndexToName(I: integer): string;
begin
  result:='';
  if (I and 1)<>0 then result:=result+'A';
  if (I and 2)<>0 then result:=result+'B';
  if (I and 4)<>0 then result:=result+'C';
  if (I and 8)<>0 then result:=result+'D';
end;end.运算结果完全符合要求,请楼主结贴吧,我可是用了好几个小时呀.再开贴给分吧.

Answer 6

首先,有以下几条原则:
1.BCD和ACD是最优的组合,因为可以取得最小的代价.
2.ABCD不能和CD,AC,AD,BC,BD共存,因为(ABCD+CD=ACD+BCD;ABCD+AC=ACD+ABC....)基于以上原则,我的处理过程是:
1.先组成尽量多的BCD或ACD的组合.在组成过程中,如果A,B有剩余,应尽量减小它们的差距,以利于下一步的两两组合.
2.剩余的组合尽量的两两组合,使剩下的某个元素最少.
3.把最后剩下的元素,按照最小权值的次序插入到已形成的组中.(也就是上面的JoinA,JoinB,JoinC,JoinD是个过程)

Answer 7

Cipherliu(孤鹰)
辛苦了！谢谢！，我调试一下。

Answer 8

Cipherliu(孤鹰)
还是有问题，如11A+5B+0C+0D 就分解不出来。应该是：
AB
AB
AB
AB
AB
A
A
A
A
A
A
==165元
这是才最小的。

Answer 9

分析(2)A+B+C或A+B+D 　　　　　　 23元 
  由A+B+C = 23 ,A+B+D = 23 得知 C = D
分析(3)B+C+D或A+C+D 　　　　　　 19元
  由B+C+D = 19, A+C+D 得知 A = B
分析(4)A+B,A+C,A+D,B+C,B+D,C+D,　15元
  1. 由 A+B = 15,A+C = 15 ,A+D = 15 得知 B = C = D
  2. 由 B+C = 15 ,B+D = 15,C+D = 15 且B = C = D,得知 B = 7.5, C = 7.5, D = 7.5
  3. 由 1,2 得知 A = 7.5
由上分析,该题严重存在逻辑上的问题.没有答案

Answer 10

lym2003(阿懋)恐怕是完全没看懂题,这不是解方程,是求分解.

Answer 11

其中，A，B，C，D权值是取那11个元素中最小的一个做为自己的权值。如有组合就不能为单独存在，否则就允许存在。

Answer 12

如果单独的元素允许存在,只需要把程序中的这段去掉即可.
  if not CanSolved() then
  begin
    ShowMessage('问题无解');
    exit;
  end;
同样可以求出最优解

Answer 13

没有，不会的。
  if not CanSolved() then
  begin
    ShowMessage('问题无解');
    exit;
  end;
应该要有最值。

Answer 14

不是，如果ABN改变，就不能算出来了。我希望的是动态的。辛苦了，在这儿先谢谢您！