高分求一类似背包算法，等着急用阿，感激不尽！！！！！！！！

学习学习！！！

顶...

不喜欢写这样的程序----代码很长，但思路很直白...
这贴子还是22号发布的呢，不知楼主是否还关注着这事儿，如果真想用的话给个电子邮箱，明天没事儿时给你写一个出来----最优化的部分还似乎有点意思。
继续关注楼主的回音...

to 回复人： QuickKeyBoard
    my email:geniusqing@hotmail.com
先谢过了

我已经给你把可执行文件发到邮箱里去了，请注意查收。

这个问题我用了很长时间，最终的结果也不令我满意，原因在于它的最优化问题:楼主说这类似于背包问题，实际上不是，这是个np hard问题，可以简述为：有若干个物品要装走，每个的重量为w(i)，同样大小的箱子足够用，但每个只能装最多M的重量，问最少要用多少个箱子。
我同我的朋友侯启明同学（清华大学大三学生，noi国际金牌获得者）讨论了一下这个问题，结果是目前还找不到多项式级的有效算法可以解决这个问题。
所以，最终，我采用的是贪心法，可以得到一个“比较”不错的解。

如果楼下有朋友可以想到多项式级的有效算法，请一定贴个答案上来，不胜感激。
下面，我将我的代码写出来，世外的高人给看看有什么错误没有。由于我事先不知道问题的最大规模，所以，没有使用穷举的办法解决。
windowsxp sp2 delphi7 下通过，纯api win32程序：

program Bag;

{$R 'XP.res' 'XP.rc'}
{$R 'RES.res' 'RES.RC'}

uses
  Windows, Messages, CommDlg;

{$include res.inc}

const
  MINLEN = 30;
  MAXSUM = 200;

type
  TNode = record
    ID, Len, Bag: Integer;
    Col: Char;
  end;
  TNodeArray = array of TNode;

var
  Good: array ['A'..'Z'] of TNodeArray;
  Bad: TNodeArray;
  BagID: Integer;

procedure ReadData(fn: PChar);
var
  temp: TNode;
  f: TextFile;
  c: Char;
begin
  { Init. }
  FillChar(Good, 26 * SizeOf(TNodeArray), 0);
  Bad := nil;

  { Read data. }
  AssignFile(f, fn);
  Reset(f);
  while not Eof(f) do
  begin
    Read(f, temp.ID, temp.Len, temp.Col);
    while (temp.Col < 'A') or (temp.Col >'Z') do
      Read(f, temp.Col);

    if temp.Len >= MINLEN then
    begin
      SetLength(Good[temp.Col], High(Good[temp.Col]) + 2);
      Good[temp.Col, High(Good[temp.Col])] := temp;
    end
    else
    begin
      SetLength(Bad, High(Bad) + 2);
      Bad[High(Bad)] := temp;
    end;
  end;
  CloseFile(f);
end;

procedure SplitBag(var bs: Integer; var d: TNodeArray);
var
  remain: array of integer;
  n, i, j, m, p: Integer;
  test: Boolean;
  temp: TNode;
begin
  n := 1;
  test := true;
  while test do
  begin
    SetLength(remain, n);
    for j := 0 to n - 1 do
      remain[j] := MAXSUM;

    for i := 0 to High(d) do
    begin
      m := 0;
      for j := 0 to n - 1 do
        if remain[j] > m then
        begin
          m := remain[j];
          p := j;
        end;

      if m >= d[i].Len then
      begin
        d[i].Bag := p + bs;
        Dec(remain[p], d[i].Len);
      end
      else
        break;
    end;

    if i > High(d) then
      test := False;

    Inc(n);
  end;

  Inc(bs, n - 1);

  for i := 0 to High(d) - 1 do
    for j := i + 1 to High(d) do
      if d[i].Bag > d[j].Bag then
      begin
        temp := d[i];
        d[i] := d[j];
        d[j] := temp;
      end;
end;

procedure WriteOut(fn: pChar);
var
  c: Char;
  i, j: integer;
  f: TextFile;
begin
  { Calculate and save result. }
  AssignFile(f, fn);
  ReWrite(f);
  Writeln(f, '序号':5,  '数量':5, '色光':5, '包号':5);
  j := 1;
  for c := 'A' to 'Z' do
    if Good[c] <> nil then
    begin
      SplitBag(j, Good[c]);
      for i := 0 to High(Good[c]) do
        Writeln(f, Good[c, i].ID:5, Good[c, i].Len:5, Good[c, i].Col:5, Good[c, i].Bag:5);
      Writeln(f);
    end;
  Writeln(f);
  SplitBag(j, Bad);
  for i := 0 to High(Bad) do
    Writeln(f, Bad[i].ID:5, Bad[i].Len:5, Bad[i].Col:5, Bad[i].Bag:5);
  CloseFile(f);

  // Free Memory
  for c := 'A' to 'Z' do
    Good[c] := nil;
  Bad := nil;
end;

function DlgProc(hWnd: HWND; Msg: WORD; wParam: WPARAM; lParam: LPARAM): LRESULT; stdcall;
var
  ofn: OPENFILENAME;
  fn: PChar;
begin
  GetMem(fn, 300 * SizeOf(Char));
  FillChar(ofn, SizeOf(OPENFILENAME), 0);
  ofn.lStructSize := SizeOf(OPENFILENAME);
  ofn.hWndOwner := hWnd;
  ofn.hInstance := hInstance;
  ofn.lpstrFilter := '文本文件(*.TXT)'#0'*.TXT'#0#0;
  ofn.lpstrFile := fn;
  ofn.nMaxFile := 300;
  ofn.lpstrDefExt := 'TXT';
  ofn.Flags := OFN_OVERWRITEPROMPT;

  case Msg of

  WM_INITDIALOG:
    Result := 1;

  WM_CLOSE:
    EndDialog(hWnd, 0);

  WM_COMMAND:
    case LOWORD(wParam) of

    IDC_READ:
      if GetOpenFileName(ofn) = True then
      begin
        ReadData(fn);
        EnableWindow(GetDlgItem(hWnd, IDC_WRITE), True);
      end;

    IDC_WRITE:
      if GetSaveFileName(ofn) = True then
      begin
        WriteOut(fn);
        EnableWindow(GetDlgItem(hWnd, IDC_WRITE), False);
      end;

    end;// case LOWORD(wParam) of

  end;// case Msg of

  Result := 0;

  FreeMem(fn);
end;// function

begin
  DialogBox(hInstance, MAKEINTRESOURCE(MAINWINDOW), 0, @DlgProc);
end.