首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 一个有意思的问题---高效地截取管子的问题,算法.高分求解!
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 结帖率：
    发表于：2008-04-30 11:50:08 楼主
    今天上午遇到了一个有意思的情况.
    一家公司需要设计这样一款软件
    具体的业务需求是这样的
    这家公司是制作门窗的,材料是铝合金管 例如:6.3米一根
    一根长管可能需要截取不同长度的小段.例如可能截取1米一段,2米一段,0.5米一段.具体如何截取和生产的产品大小规格有关.
    希望编写一个软件,可以把材料利用律最大化.
    软件主要有两类不同的参数
    一类:需要输入截取几种不同长度的小段的长度.例如:1米,1.5米等.
    二类:进料的长度.例如6.3米
    目前小弟还没有拿出好的办法,各位老大有什么好的想法.
    在线等待
    100  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 11:58:141楼 得分:0
    再补充说下:
    原材料是成批购买的,例如可能买50根 6.3米的管子.
    截取的小段也是很多可能需要截取20根1米的,20根1.5米的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • C1053710211
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 12:13:182楼 得分:0
    动态规划，建立一个表示管子总长度的数组d，
    对于d[i]，如果能够截取出长度为i的管子，那么d[i]为1,否则为0;
    状态转移方程
    if d[i-l[j]]==1 ，d[i]=1，l[j]是可供选择的那些截取长度，0 <j <n,
    else d[i]=0 ,d数组中下标最大那个为1的i就是所求。
             
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yatobiaf
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 12:58:063楼 得分:0
    动态规划啊，典型的背包问题。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 13:55:414楼 得分:0
    谢谢!
    刚才看了下"背包问题",有点晕.希望能再详细点.
    我再补充下:"就是说，一天当中现在需要截成什么样的东西，要截多少知道，现在就是想对每一根料怎么截，才能使用的料最少"
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 14:32:485楼 得分:0

    刚才又询问了下,答复说"能确定的是一天当中的需求量能提供出来，多少个小段的管子,什么规格的.现在就是想对每一根料怎么截，才能使用的料最少"
    我感觉这个问题和背包问题有些差异啊
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 7

      6
    发表于：2008-04-30 14:33:476楼 得分:0
    不妨设大管子的长度为L（假设有足够多的备货），需要截成的小管子数量和长度分别为：
    n[1]个长度为L[1]的小管子、n[2]个长度为L[2]的小管子、……、n[k]个长度为L[k]的小管子。
    假设截取方案中一共用到了m根大管子，那么浪费的材料长度为：
    m*L-n[1]*L[1]-n[2]*L[2]-…-n[k]*L[k]
    我们要使浪费的材料最少，也就使m最小。换句话说，怎样用最少根数的大管子就能裁出符合要求的小管子？

    另外用一个模型更容易理解这个问题：小明是个旅游爱好者，现在他准备趁着五一假期出门旅游。他家里有足够多的容积为L的（一模一样的）背包。小明清点了一下旅途中要带的物品：体积为L[1]的有n[1]件、体积为L[2]的有n[2]件、……、体积为L[k]的有n[k]件，怎样用最少数量的背包就能把这些东西全都放下？

    解决办法：
    1)把这看成一个容积限制为L的0－1背包问题，先来填第一个背包；
    2)所有物品是否已经全都放进去了？
          如果是，算法结束；
          如果没有，对剩下的物品再使用0-1背包的方法再填充一个容积为L的背包；
    3)重复2
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 15:04:097楼 得分:0
    谢谢,dlyme:
    经典的背包问题中,价格是不是一个干扰?如果把价格问题去掉?
    令为了验证是不是最优方案,是否要把"m*L-n[1]*L[1]-n[2]*L[2]-…-n[k]*L[k]"公式代入演算啊?
    还有很多问题不明确,希望能给出详细的解答.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 7

      6
    发表于：2008-04-30 15:54:078楼 得分:0
    价格？这里面没有涉及到价格，或者可以认为所有物品的价格是和体积/重量成正比的，所以只考虑体积/重量一个因素就够了。

    那个公式是用来说明问题的（用的管子越少越省料），但无法直接用来演算。因为具体用到多少根大管子是受小管子数量和长度影响的，不能直接套公式。举个例子来说：大管子长6.3米，现在需要截出3根长4米的小管子，如果直接看公式6.3*2>4+4+4，好像用两根就可以了，但实际上需要3根才能裁出来。

    这个解答其实已经很清楚了，你的问题还是在于对0-1背包问题不了解。关于这方面的资料网上有很多，建议你先看看。

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • brucesea
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 16:01:309楼 得分:0
    先贴个代码，没时间解释了，
    也不知道对不对，回去再看看

    C/C++ code
    

double size[3] = {0.5, 1, 2};
pair<int, double> dp[100][100][100];
double material = 6.3;

pair<int, double> get(pair<int, double>& p, int id)
{
    if (size[id] > p.second)
        return (make_pair(p.first+1, material - size[id]));
    return (make_pair(p.first, p.second - size[id]));
}

pair<int, double> go(int n1, int n2, int n3)
{
    if (dp[n1][n2][n3].first != -1) return dp[n1][n2][n3];

    pair<int, double> p1, np1, p2, np2, p3, np3;
    np1.first = np2.first = np3.first = INT_MAX;
    if (n1 > 0) 
    {
        p1 = go(n1-1, n2, n3);
        np1 = get(p1, 0);
    }
    if (n2 > 0) 
    {
        p2 = go(n1, n2-1, n3);
        np2 = get(p2, 1);
    }
    if (n3 > 0) 
    {
        p3 = go(n1, n2, n3-1);
        np3 = get(p3, 2);
    }

    pair<int, double> minp = min(min(np1, np2), np3);
    dp[n1][n2][n3] = minp;

    return minp;
}

void cal()
{
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            for (int k = 0; k < 100; k++)
                dp[i][j][k] = make_pair(-1, 0);

    dp[0][0][0].first = 0;
    dp[0][0][0].second = 0;

    go(10, 20, 30);

    cout << dp[10][20][30].first << endl;
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • joners
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-01 10:02:5510楼 得分:0
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • knowledge_Is_Life
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-01 18:29:1411楼 得分:0
    以后需再关注，现在先帮你顶一下
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rover___
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-01 21:11:2912楼 得分:0
    6.3米分成1米,1.5米这2种的话，没什么好优化的。1米,1.5米的价格如何不明白的话，只能按照其尺寸定价。6.3米分成6个1米,4个1.5米，2个1.5米和3个1米，都是最优解。除非能给出不同尺寸材料的价格来，要不没法整体优化。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      3

      2
    发表于：2008-05-02 00:32:5713楼 得分:0
    这个问题直接用0-1背包应该有点问题;

    比如大管子的长度为8米;
    现在需要8个5米的,以及8个2米的;

    如果用背包,那么前两根大管子就会被裁成8根2米的;
    这样就需要10跟大管子;

    但每根大管子都裁成5+2,只需要8根;
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • brucesea
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-02 09:19:3214楼 得分:0

    原来的代码求最优解部分min搞错了，改一下。

    代码含义：
    pair <int, double> dp[100][100][100];

    这儿假设有三种可能的截取长度，
    dp[n1][n2][n3]用于保存对应于每种截取长度所需个数为n1,n2,n3时的最优解，
    pair <int, double>中int用于保存材料个数，double用于保存当前剩余长度。

    dp[n1][n2][n3]可以由dp[n1-1][n2][n3],dp[n1][n2-1][n3],dp[n1][n2][n3-1]中最优的一个获得，
    参考代码。

    可能存在的问题：
    内存消耗。如果有k种可能的截取长度，每种最大需要的个数为Ni，
    如果N1*N2*...*Nk内存可以接受的话，动态分配dp的大小，这儿的解法可能没什么问题。
    如果内存过大，可以采用map，以(n1,n2,...,nk)作为索引。

    C/C++ code
    

double material = 6.3;
double size[3] = {0.5, 1, 2};
pair<int, double> dp[100][100][100];

pair<int, double> get(pair<int, double>& p, int id)
{
    if (size[id] > p.second)
        return (make_pair(p.first+1, material - size[id]));
    return (make_pair(p.first, p.second - size[id]));
}

pair<int, double> minp(pair<int, double>& p1, pair<int, double>& p2)
{
    if (p1.first < p2.first) return p1;
    if (p1.first == p2.first)
    {
        if (p1.second > p2.second) return p1;
    }
    return p2;
}

pair<int, double> go(int n1, int n2, int n3)
{
    if (dp[n1][n2][n3].first != -1) return dp[n1][n2][n3];

    pair<int, double> p1, np1, p2, np2, p3, np3;
    np1.first = np2.first = np3.first = INT_MAX;
    if (n1 > 0) 
    {
        p1 = go(n1-1, n2, n3);
        np1 = get(p1, 0);
    }
    if (n2 > 0) 
    {
        p2 = go(n1, n2-1, n3);
        np2 = get(p2, 1);
    }
    if (n3 > 0) 
    {
        p3 = go(n1, n2, n3-1);
        np3 = get(p3, 2);
    }

    pair<int, double> min0 = minp(minp(np1, np2), np3);
    dp[n1][n2][n3] = min0;

    return min0;
}

void cal()
{
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            for (int k = 0; k < 100; k++)
                dp[i][j][k] = make_pair(-1, 0);

    dp[0][0][0].first = 0;
    dp[0][0][0].second = 0;

    go(10, 20, 30);

    cout << go(10, 20, 30).first << endl;
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baobao2010
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-02 09:27:1615楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      3

      2
    发表于：2008-05-02 09:48:4016楼 得分:0
    感觉
    brucesea
    可口可乐的解法是可以的；

    如果将每个小管子都进行编号，那么每一种裁法都可以对应到一个排列；
    其中的每一个小管子要么跟上一小管子用同一管子，要么使用一个新的管子；
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • junglesong
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-12 13:51:1917楼 得分:0
    mk
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • swbchangle
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-12 16:47:1518楼 得分:0
    明显是数学建模的题目

    先确定切割模式：

        模式i      截取a1长度的数量ri1，截取a2长度的数量ri2，截取a3长度的数量ri3，……，剩余长度（下脚料）ri

    列出所有的模式。（规模较大的话得用程序实现）

    设x1，……，xn为按照各种模式切割的钢管数

    决策目标为Min x1+x2+……+xn

    约束条件
          根据要求列出方程组

          为优化程序，可以加上x1>=x2>=……>=xn，因为各种模式的排列顺序无关

    然后 用LINGO求解

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • aayzaayz
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-02 14:16:5919楼 得分:0
    ....
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Paradin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2009-05-05 16:58:0720楼 得分:0
    感觉不是背包问题吧。。。是bin-packing

    1)把这看成一个容积限制为L的0－1背包问题，先来填第一个背包；
    2)所有物品是否已经全都放进去了？
          如果是，算法结束；
          如果没有，对剩下的物品再使用0-1背包的方法再填充一个容积为L的背包；
    3)重复2

    你看看我举这个例子有问题不：

    包容积为10
    10个物品体积为2 2 2 2 2 7 7 7 7 7

    用背包的话：
      第1个包: (2,2,2,2,2)
        2    : (7)
        3    : (7)
        ..  ...
        6:    (7)
    一共6个包。
    而实际上只要5个： (2,7) (2,7) (2,7) (2,7) (2,7)

    不知道是不是我理解错了。。

    我顶18楼
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Paradin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2009-05-05 17:00:0521楼 得分:0
    引用 16 楼 tailzhou 的回复:
    感觉
    brucesea
    可口可乐的解法是可以的；

    如果将每个小管子都进行编号，那么每一种裁法都可以对应到一个排列；
    其中的每一个小管子要么跟上一小管子用同一管子，要么使用一个新的管子；


    那个是不是就是穷举啊？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Paradin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2009-05-05 21:53:2322楼 得分:0
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • bobniq
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2009-05-07 11:09:4023楼 得分:0
    down
    修改 删除 举报 引用 回复
    公司简介| 广告服务| 银行汇款帐号| 联系方式| 版权声明| 问题报告
    北京创新乐知广告有限公司 版权所有, 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    文明办网文明上网举报电话：13552009689
    Copyright © 1999-2009, CSDN.NET, All Rights Reserved
    GongshangLogo