一个数学问题

[Eyon]

已知有7种棍子长度，分别为 31cm、47cm、57cm、73cm、87cm、102cm、117cm，问：若只选择其中3种长度的棍子，到底选择哪三种长度能够在尽量少用棍子根数的情况下，让棍子能尽量连接成1000cm以内的任意长度。

[stackpop]

背包问题？

[ob]

任意长度？32cm怎么连？

[Todd_Leo]

@ob "尽量"

[heian0224]

对于a b c三种长度，凑成1000cm以内的一个长度l对应的分配方案为al，bl，cl
这个分配方案需要棍子根数为pl，（可能几种，pl为最少的棍子根数）然后将这些数据存储在p[1000]的数组中，没有分配方案的置为0，然后这个数组中非0元素个数为n，n/1000记为达成率。棍子总数为数组中全部元素的和m。
然后用循环讲7种取3种的组合方案实现进行比较n取最大保存在一个三维数组中，n相同情况再比较m。
算法大概是这样的。笔算好复杂，还是机器来算吧。

[blacktulip]

感觉题目有问题，两个「尽量」会有冲突。

[littlewey]

觉得可能有问题，如果两种方案各自包含对方无法组成的长度，如何评判哪个更好？靠能占的不同长度的方案数量？

[dingyaguang117]

@blacktulip 2个尽量 应该有个优先级

[imn1]

高人指教下 30cm、32cm 怎么选？

[Exin]

如楼上所说，题目不太清楚

[Eyon]

我是 lz，第一个“尽量”优先级更大一些

[Eyon]

@heian0224 没太懂，这个能用个程序来算出吗？

[Eyon]

@littlewey 使用棍子根数最短的更好。

[heian0224]

@Eyon 算法是可以实现的。不过这里是问数学问题，其实问的应该是数论的问题，要的回答应该不是程序来实现。不过我的理解感觉是长度达成率优先级更高，因为棍子根数少的话，选择最后三种来实现1000cm以内长度的分配不是最少的吗