V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qinjiannet
V2EX  ›  程序员

一个最优化问题

  •  
  •   qinjiannet · 2016-12-15 15:49:55 +08:00 · 3965 次点击
    这是一个创建于 2660 天前的主题,其中的信息可能已经有所发展或是发生改变。

    观察下面的表格

       B1 B2 B3 B4
    A1 9  9  8  3   10
    A2 2  6  4  4   40
    A3 8  9  3  4   30
    A4 3  3  5  2   60
    A5 9  9  1  6   90
       50 60 50 70
    	
    

    上表中 A1~A5 表示 5 家快递公司, B1~B4 表示 4 种商品,矩阵内的值表示快递公司运送某种商品的单价。

    矩阵右侧的值表示各家快递公司需要运送的商品总数

    矩阵下方的值表示每种商品的总数

    求满足上述约束条件的最小运费

    第 1 条附言  ·  2016-12-15 17:12:18 +08:00
    每一家快递公司运送货物的总数必须等于其所在行最右侧的值

    每一种货物的运送总数必须等于其所在列最下方的值
    29 条回复    2016-12-23 16:19:15 +08:00
    liuzhster
        1
    liuzhster  
       2016-12-15 16:11:59 +08:00
    多重背包问题?
    goodryb
        2
    goodryb  
       2016-12-15 16:14:06 +08:00
    下表不是从 0 开始,差评
    Kilerd
        3
    Kilerd  
       2016-12-15 16:14:41 +08:00
    感觉楼上说对了,可以试试。 这种就是背包模型嘛。
    q397064399
        4
    q397064399  
       2016-12-15 16:52:51 +08:00
    动态规划题,╮(╯▽╰)╭ 先把递归公式写出来吧,写出来就差不多了
    q397064399
        5
    q397064399  
       2016-12-15 16:56:30 +08:00
    个人建议 不会背包 或者 背包不熟悉 ,这种题目 直接给它穷举就好了
    ArieShout
        6
    ArieShout  
       2016-12-15 18:46:50 +08:00 via iPhone
    前面几位回答就像数学答案上面的“易得”,“显然”一样呃
    justyy
        7
    justyy  
       2016-12-15 19:18:43 +08:00
    个人感觉应该是动态规化,可是我写不出来公式。。有大牛教教 我么?
    如果 A 只有 5 个, B 只有 4 个, 完全可以暴力。
    qinjiannet
        8
    qinjiannet  
    OP
       2016-12-15 19:52:00 +08:00
    @q397064399 这个问题穷举的复杂度是多少?
    wodesuck
        9
    wodesuck  
       2016-12-15 22:21:32 +08:00
    为什么这么多人说是背包?
    我觉得是个费用流啊。
    求背包状态转移方程。
    billgreen1
        10
    billgreen1  
       2016-12-15 23:36:14 +08:00   ❤️ 1
    如果商品是整数,那么是整数规划问题,有现成的软件包的
    q397064399
        11
    q397064399  
       2016-12-16 05:32:06 +08:00
    @qinjiannet 排列组合就好,自己算吧
    q397064399
        12
    q397064399  
       2016-12-16 05:38:01 +08:00
    @ArieShout
    不是显然,或者易得, 刷 OJ 的人 大多都会临时突击 各种算法 ,
    目的是啥,不还是套路,既然出了这个题目,就证明这个问题是计算可行性的,那不就是套路了,
    万千世界,其实就一个套路 就可以解释,万物所有的规律 包括 牛顿定律 啥的 都是套路,
    这题就算不是 DP 也跟 DP 差的八九不离十,
    q397064399
        13
    q397064399  
       2016-12-16 06:00:21 +08:00
    @qinjiannet

    但是穷举有一个问题,要排除无效集
    穷举的思路 是针对限定条件的,例如

    B1 B2 B3 B4
    A1 9 9 8 3 10
    A2 2 6 4 4 40
    A3 8 9 3 4 30
    A4 3 3 5 2 60
    A5 9 9 1 6 90
    50 60 50 70

    这里 10 40 30 60 90 就是一个限定条件,

    显然可以通过枚举计算出 10 40 30 60 90 ,分别 由 4 个整数组成的 排列组合,

    这样就枚举出来 所有 A1 快递公司所能 运送 4 种商品的 条件集合

    快递公司的运送不同商品的结果集计算复杂度 O(n4)

    貌似还有更优的算法,不过我了解过(如果有知道的 可以告知我一声)

    A1 计算次数是 ( 10 ) 4 次方
    A2 计算次数是 ( 40 ) 4 次方
    ..
    A5 的计算次数是( 90 ) 4 次方

    依次下来 通过过滤
    就能得到所有快递公司 运送这 4 种商品的可行性集合,
    (但是这个可行性集 并不满足货物数量的限定条件)

    然后再从这个集合中,找出 符合( 50 60 50 70 )的集合


    最终从这个合法的集合当中 排序获得最大值即可
    q397064399
        14
    q397064399  
       2016-12-16 06:03:37 +08:00
    @wodesuck
    这个问题 其实只要上过高中就能解,但是通过限定条件穷举出 合法集,是一种非常傻逼的行为,
    在会算法的程序员来看(我真不会多少算法),这种方法有点 Low 假如问题规模变大了,几乎是很难解的出来
    q397064399
        15
    q397064399  
       2016-12-16 06:09:06 +08:00
    DP 的思想 其实就是通过转移方程,将一些不必要的计算结果集 给排除掉了
    q397064399
        16
    q397064399  
       2016-12-16 06:12:31 +08:00
    再次强调,通过 X Y 的限定条件来穷举合法矩阵集的最优解 是非常 Low 的行为,

    如果有 人知道此类问题的算法叫什么名字 麻烦请告知我一声,(除了 DP )
    Xs0ul
        17
    Xs0ul  
       2016-12-16 07:21:57 +08:00 via Android   ❤️ 1
    看起来像是线性规划(
    zouxy
        18
    zouxy  
       2016-12-16 07:34:27 +08:00 via iPhone
    好像叫 单纯形法
    zouxy
        19
    zouxy  
       2016-12-16 07:36:52 +08:00 via iPhone   ❤️ 1
    华罗庚主持编写那本绿色封面 运筹学 上有
    BBrother
        20
    BBrother  
       2016-12-16 09:24:22 +08:00
    有种运筹学作业的既视感
    sengxian
        21
    sengxian  
       2016-12-16 13:32:23 +08:00
    sengxian
        22
    sengxian  
       2016-12-16 13:33:29 +08:00   ❤️ 1
    啊不好意思上面鼠标截下来了
    sengxian
        23
    sengxian  
       2016-12-16 13:38:47 +08:00
    这个题网络流的点数是 $O(n + m)$,边数是 $O(nm)$ 的,鉴于网络流的复杂度都比较高,所以大概只能跑几百的数据。
    qinjiannet
        24
    qinjiannet  
    OP
       2016-12-16 13:45:31 +08:00
    @sengxian 图中的(a, b)表示容量为 a ,初始流量为 b 吗?
    sengxian
        25
    sengxian  
       2016-12-16 14:05:58 +08:00 via iPhone   ❤️ 1
    容量为 a ,费用为 b 。
    peihanw
        27
    peihanw  
       2016-12-19 10:26:31 +08:00
    典型线性规划问题,用 GLPK 写一个 model 定义文件,秒解。
    hannah520
        28
    hannah520  
       2016-12-23 16:17:06 +08:00   ❤️ 1
    122
    hannah520
        29
    hannah520  
       2016-12-23 16:19:15 +08:00   ❤️ 1
    啊啊啊啊,竟然回答也需要铜币!重新回答一次吧
    数学模型:
    *******************************并不造如何上传公式或者图片**************************************
    matlab 求解:
    function [f]=transport(x)
    f=0;
    C=[7 1 1 6 3 3 7 6 9 7 9 5 4 2 5 8 7 1 3 9];
    for i=1:20
    f=f+x(i)*C(i);
    end
    end

    lb = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
    ub = [Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf];
    x0 = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
    Aeq = [1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
    0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
    0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
    0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;
    1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
    0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
    Beq = [30 90 30 60 70 30 50 40 20];
    [x,f] = fmincon(@transport,x0,[],[],Aeq,Beq,lb,ub)

    结果如下:
    x =

    1 至 13 列

    0.0000 39.1780 30.0000 0.8220 20.8220 0.0000 0.0000 9.1780 0.0000 0.0000 0.0000 50.0000 9.1780

    14 至 20 列

    30.8220 0.0000 0.0000 0.0000 20.0000 0.0000 0.0000


    f =

    560.0000
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3449 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 11:12 · PVG 19:12 · LAX 04:12 · JFK 07:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.