背包问题是不是有多种变种？ <- 中国开发网

CNDEV.ORG

当前在线

论坛

CBD
- 程序员情感CBD
- 程序员见面交流会
CBD开发区
- Java/J2ME
- .NET/C#
- 数据库
- Delphi/BCB
- Visual C
其它
情感
游戏
- CNDEV-CS/WOW
- 浩宇长空
生活
论坛系统

haitao：

背包问题是不是有多种变种？

[阅读: 531] 2006-05-08 14:42:44

输入：
“体积-重量”对的数组
目标：
1、指定元素个数，要求所选的元素的总重量最大
2、指定最后的体积最大值，要求所选的元素的总重量最大
（元素个数没限制，只要求总体积不得大于指定值）
3、指定一个总重量值，要求所选的元素的总重量最接近它
（元素个数、总体积没限制）

我的blog：http://szhaitao.blog.hexun.com & http://www.hoolee.com/user/haitao

－－以上均为泛泛之谈－－不尽牛人滚滚来，无边硬伤纷纷现人在江湖飘（出来混的），哪能不挨刀（总归是要还的）
网络对话，歧义纷生；你以为明白了对方的话，其实呢？

您所在的IP暂时不能使用低版本的QQ，请到：http://im.qq.com/下载安装最新版的QQ，感谢您对QQ的支持和使用

相关信息:

悄悄问一下：有没有啥现成的可以从一堆数里抽出若干个数，这若干个数之和等于或最接近于某个指定的值的程序？ (89字) (ycm0263 [936] 2006-05-08 03:28)
- 懒得去写排列程序？ (32字) (haitao [439] 2006-05-08 03:33)
  - 你觉得这个程序值多少钱？ (65字) (ycm0263 [419] 2006-05-08 04:00)
    - 1000RMB吧 (32字) (Fish [367] 2006-05-08 04:08)
      - 偶是代 haitao 问他们的。 (185字) (ycm0263 [354] 2006-05-08 04:22)
        写成console程序，用 printf 或者 cout 吧 (空) (Fish [351] 2006-05-08 04:29)
        偶们平时就是用 cout 的，可他们看不惯字符界面吖。 (17字) (ycm0263 [378] 2006-05-08 04:30)
        写程序是要静下来才行。。。 (92字) (haitao [341] 2006-05-08 04:30)
        背包/遗传算法都是现成的。 (空) (ycm0263 [423] 2006-05-08 04:34)
    - 明确一下需求 (101字) (haitao [396] 2006-05-08 04:22)
      - 没那么复杂。数据个数不超过 40 个，每个数据都是 1000 以内的自然数。 (15字) (ycm0263 [519] 2006-05-08 04:28)
        背包/遗传算法？？ (88字) (haitao [483] 2006-05-08 04:33)
        这问题需要全枚举吗？ (空) (ycm0263 [379] 2006-05-08 04:43)
        “等于或最接近于”，应该就意味着是最优解，而不是较优解吧 (64字) (haitao [389] 2006-05-08 04:53)
        应该有吧。这又不是什么很新鲜的算法。 (空) (ycm0263 [311] 2006-05-08 04:58)
        不怕，可以多core多cpu算 (空) (lukejee [313] 2006-05-08 15:25)
        就这点运算量还要多 core 多 cpu？ (空) (ycm0263 [377] 2006-05-08 15:57)
        就一个国际象棋的棋盘，能骗走多少粮食。。。 (8字) (haitao [423] 2006-05-08 16:15)
        知道。 (21字) (ycm0263 [303] 2006-05-08 16:16)
        知道什么是阶乘吗 (39字) (haitao [840] 2006-05-08 16:56)
        那就Multi Core吧，再不成SMP,再不成俺们搭Cluster, 后勤部钞票应该不少吧 (12字) (lukejee [337] 2006-05-08 17:03)
        当然知道。不过， (78字) (ycm0263 [473] 2006-05-08 18:33)
        这个问题是通过组合递增函数来排除的 (5字) (haitao [336] 2006-05-09 00:46)
        你就不能稍微加一点判断，把一看就知道不需要的部分去掉？ (空) (ycm0263 [337] 2006-05-09 00:48)
        什么叫通用。。。 (39字) (haitao [412] 2006-05-09 00:57)
- 背包算法？ (空) (sealw [433] 2006-05-08 03:34)
  - 背包问题是不是有多种变种？ (147字) (haitao [530] 2006-05-08 14:42)
    - 第一个问题不是背包算法解决的范畴。 (空) (ycm0263 [407] 2006-05-08 15:05)
- 赌博用的？ (空) (pcplayer [288] 2006-05-08 14:55)
  - 不是。是后勤部的人要用的。以前他们都是用小工来做的，后来不知道他们怎么发现偶算这些特别快，就总为这种事来找偶了。 (空) (ycm0263 [391] 2006-05-08 15:06)
    - 当然啦，不然你总是IDLE，太浪费资源了。 (空) (zhong [316] 2006-05-08 15:10)
      - ╭∩╮（︶︿︶）╭∩╮ (空) (ycm0263 [308] 2006-05-08 15:11)
    - 此贴为显摆贴. (空) (nostalgic [321] 2006-05-08 23:57)
      - 擅长做小工也叫显摆？ (空) (ycm0263 [358] 2006-05-09 00:08)
        显摆机器人的AI就是显摆了 (空) (oyjt [323] 2006-05-09 01:06)
- 问题：比如有2种可能：A，有8 个数加起来等于你要的数字；B。有3个数字加起来等于你要的数字。需求里是否要求找到最少的数字个数？还是找到一组就算？ (空) (pcplayer [680] 2006-05-08 14:59)
  - 找到一组就 OK。 (47字) (ycm0263 [334] 2006-05-08 15:11)
    - 俺不懂什么背包算法，俺没背过别人的包。我想，是不是做减法比较好？ (空) (pcplayer [473] 2006-05-08 15:26)
      - 加法做起来容易一点。 (空) (ycm0263 [339] 2006-05-08 15:58)
        你要的数字是结果，我拿结果减去第一个数，再减去第二个数....减到0为止。 (空) (pcplayer [409] 2006-05-08 16:06)
        理论上差不多，不过用加法做起来好处理一些。 (空) (ycm0263 [346] 2006-05-08 16:10)
- 你们不要讨论了，这点时间早写出来了 (空) (lukejee [351] 2006-05-08 16:16)
  - 我倒是觉得很有必要。。。 (103字) (haitao [411] 2006-05-08 17:00)
    - 参考这个： (131字) (ycm0263 [406] 2006-05-08 18:36)

欢迎光临本社区，您还没有登录，不能发贴子。请在这里登录

页面内容处理时间: 0.022 - 647432