热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

通常打包要求有:1、码长限制;2、色光(A、B色);3、装箱限量(就是限制这一箱装多少米);其中码长通常为一范围,色光为:A、B、C、D之类例:现假设有一批货,代号为:0081、码
通常打包要求有:1、码长限制;2、色光(A、B色);3、装箱限量(就是限制这一箱装多少米); 
其中码长通常为一范围, 色光为:A、B、C、D之类

例:现假设有一批货,代号为:008
1、码长要求为 ≥30米;    
2、装箱限量≤200米
原始数据库中的数据(图1):                    
序号   数量(米)  色光  包号
1 60 A
2 70 B
3 80 A
4 20 A
5 40 B
6 50 C
7 70 A
8 30 A
9 50 B
10 18 B

 开始计算结果如下(图2)

序号 b 数量(米) 色光 包号
1 60 A 1
3 80 A 1
7 70 A 2
8 30 A 2
2 70 B 3
5 40 B 3
9 50 B 3
6 50 C 4
4 20 A 5
10 18 B 5

注:1、在上例中,先剔除码长不符合要求的,然后再成件。
2、色光相同的要成在一个件中。
a.刚开始先把码长不符合要求的(码长要求为 ≥30米),如4号和10号放最下面
b。在色光A中按顺序数量相加,如60+80<200,若60+80+70=210>200,不符合要求,则包号为1。再次在色光为A中剩下的按顺序数量相加,如70+30=100<200
则包号为2
同理B,C
c.码长不符合要求的不管多少通统定为最后的数字
注:图2是按输入顺序得到的,那位会最优算法的更好

5 个解决方案

#1


学习学习!!!

#2


顶...

#3


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

#4


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

#5


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

这个问题我用了很长时间,最终的结果也不令我满意,原因在于它的最优化问题:楼主说这类似于背包问题,实际上不是,这是个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.

推荐阅读
  • 第四章高阶函数(参数传递、高阶函数、lambda表达式)(python进阶)的讲解和应用
    本文主要讲解了第四章高阶函数(参数传递、高阶函数、lambda表达式)的相关知识,包括函数参数传递机制和赋值机制、引用传递的概念和应用、默认参数的定义和使用等内容。同时介绍了高阶函数和lambda表达式的概念,并给出了一些实例代码进行演示。对于想要进一步提升python编程能力的读者来说,本文将是一个不错的学习资料。 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • Go GUIlxn/walk 学习3.菜单栏和工具栏的具体实现
    本文介绍了使用Go语言的GUI库lxn/walk实现菜单栏和工具栏的具体方法,包括消息窗口的产生、文件放置动作响应和提示框的应用。部分代码来自上一篇博客和lxn/walk官方示例。文章提供了学习GUI开发的实际案例和代码示例。 ... [详细]
  • 本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析,包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤,包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ... [详细]
  • 本文详细介绍了GetModuleFileName函数的用法,该函数可以用于获取当前模块所在的路径,方便进行文件操作和读取配置信息。文章通过示例代码和详细的解释,帮助读者理解和使用该函数。同时,还提供了相关的API函数声明和说明。 ... [详细]
  • 本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法,并提供了一个范例。通过宏定义的方式,可以方便地处理不定参数的情况。文章中给出了具体的代码实现,并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说,是一个很有用的参考资料。 ... [详细]
  • 本文介绍了OC学习笔记中的@property和@synthesize,包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文介绍了在Win10上安装WinPythonHadoop的详细步骤,包括安装Python环境、安装JDK8、安装pyspark、安装Hadoop和Spark、设置环境变量、下载winutils.exe等。同时提醒注意Hadoop版本与pyspark版本的一致性,并建议重启电脑以确保安装成功。 ... [详细]
  • 在说Hibernate映射前,我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象,以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]
  • 本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用,包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • 本文介绍了一个在线急等问题解决方法,即如何统计数据库中某个字段下的所有数据,并将结果显示在文本框里。作者提到了自己是一个菜鸟,希望能够得到帮助。作者使用的是ACCESS数据库,并且给出了一个例子,希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句,得到的结果是650,但不知道如何得到560。希望能够得到解决方案。 ... [详细]
  • 本文详细介绍了如何使用MySQL来显示SQL语句的执行时间,并通过MySQL Query Profiler获取CPU和内存使用量以及系统锁和表锁的时间。同时介绍了效能分析的三种方法:瓶颈分析、工作负载分析和基于比率的分析。 ... [详细]
author-avatar
辛愿1346_589
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有