V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Eyon
V2EX  ›  问与答

一个数学问题

  •  
  •   Eyon · 2014-11-12 14:20:56 +08:00 · 3176 次点击
    这是一个创建于 3646 天前的主题,其中的信息可能已经有所发展或是发生改变。
    已知有7种棍子长度,分别为 31cm、47cm、57cm、73cm、87cm、102cm、117cm,问:若只选择其中3种长度的棍子,到底选择哪三种长度能够在尽量少用棍子根数的情况下,让棍子能尽量连接成1000cm以内的任意长度。
    13 条回复    2014-11-13 14:14:33 +08:00
    stackpop
        1
    stackpop  
       2014-11-12 15:00:20 +08:00
    背包问题?
    ob
        2
    ob  
       2014-11-12 15:26:57 +08:00
    任意长度?32cm怎么连?
    Todd_Leo
        3
    Todd_Leo  
       2014-11-12 15:31:15 +08:00
    @ob "尽量"
    heian0224
        4
    heian0224  
       2014-11-12 16:04:09 +08:00
    对于a b c三种长度,凑成1000cm以内的一个长度l对应的分配方案为al,bl,cl
    这个分配方案需要棍子根数为pl,(可能几种,pl为最少的棍子根数)然后将这些数据存储在p[1000]的数组中,没有分配方案的置为0,然后这个数组中非0元素个数为n,n/1000记为达成率。棍子总数为数组中全部元素的和m。
    然后用循环讲7种取3种的组合方案实现进行比较n取最大保存在一个三维数组中,n相同情况再比较m。
    算法大概是这样的。笔算好复杂,还是机器来算吧。
    blacktulip
        5
    blacktulip  
       2014-11-12 16:08:29 +08:00
    感觉题目有问题,两个「尽量」会有冲突。
    littlewey
        6
    littlewey  
       2014-11-12 16:27:48 +08:00
    觉得可能有问题,如果两种方案各自包含对方无法组成的长度,如何评判哪个更好?靠能占的不同长度的方案数量?
    dingyaguang117
        7
    dingyaguang117  
       2014-11-12 16:39:12 +08:00
    @blacktulip 2个尽量 应该有个优先级
    imn1
        8
    imn1  
       2014-11-12 16:54:50 +08:00
    高人指教下 30cm、32cm 怎么选?
    Exin
        9
    Exin  
       2014-11-12 17:06:56 +08:00 via iPad
    如楼上所说,题目不太清楚
    Eyon
        10
    Eyon  
    OP
       2014-11-12 20:50:18 +08:00
    我是 lz,第一个“尽量”优先级更大一些
    Eyon
        11
    Eyon  
    OP
       2014-11-12 20:54:27 +08:00
    @heian0224 没太懂,这个能用个程序来算出吗?
    Eyon
        12
    Eyon  
    OP
       2014-11-12 20:55:38 +08:00
    @littlewey 使用棍子根数最短的更好。
    heian0224
        13
    heian0224  
       2014-11-13 14:14:33 +08:00
    @Eyon 算法是可以实现的。不过这里是问数学问题,其实问的应该是数论的问题,要的回答应该不是程序来实现。不过我的理解感觉是长度达成率优先级更高,因为棍子根数少的话,选择最后三种来实现1000cm以内长度的分配不是最少的吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   986 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:25 · PVG 05:25 · LAX 13:25 · JFK 16:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.