现有如下问题:
需要总量为 300 个的水果
且满足苹果 100 个 橘子 100 个 桃子 100 个
目前要从 10 家单位中随机选取 3 家 且每家单位拿取总数(苹果+橘子+桃子)100 个
假设目前数据如下,请给出最优算法
单位名称 | 苹果 | 橘子 | 桃子 |
---|---|---|---|
A | 40 | 50 | 60 |
B | 50 | 50 | 50 |
C | 50 | 50 | 0 |
D | 100 | 0 | 100 |
E | 80 | 20 | 40 |
F | 40 | 50 | 10 |
G | 10 | 50 | 30 |
H | 20 | 20 | 30 |
I | 80 | 90 | 10 |
J | 60 | 20 | 10 |
1
yarns OP 目前两个解
1 、硬算 会出现几个单位 n 的阶乘种排序导致的结果 计算次数贼大 2 、常量特征 设置一个特征值 比如 50 根据 n 单位的苹果和橘子和桃子的差值和平均值 得出特征值 值越小越能组合成 100 按特征值来整 |
2
wlsnx 2021-09-10 11:36:48 +08:00
这怎么随机?题目是要求找出符合条件的一个解吧。
先排序,把 1 (最大)+2 最小>100 和 1 (最小)+2 最大<100 的去掉,肯定不满足条件。 然后暴力破解,假设取出先 A,把苹果>60 或橘子>50 或桃子>40 的去掉,再从剩余结果中取一个,去掉不符合条件的再取第三个,如果剩余结果为空就回溯。 |
4
wlsnx 2021-09-14 20:21:32 +08:00
|
6
wlsnx 2021-09-17 10:51:51 +08:00
你这个问题就是一个 k 数之和问题,简化一下就是在某一列做 k 数之和,再验证其他列是否也都正好合适。k 为 3 时很简单,k 为 100 时基本无解。
|
7
yarns OP @wlsnx 没法了 就用硬算了 用差值来解决了 横向之和用比例 然后算纵向之和与 100 的差值是多少 然后遍历行来补差值
|
8
yarns OP @wlsnx
name passenger cargo auto temp_sum p_count c_count a_count 0 A 40 50 60 150 27.0 33.0 40.0 1 B 50 50 50 150 33.0 33.0 34.0 2 F 40 50 10 100 40.0 50.0 10.0 差值分别为------- 0.0 : -16.0 : 16.0 耗时: 0.011885099999999982 秒 {'name': 'A', 'passenger': 27.0, 'cargo': 17.0, 'auto': 56.0} {'name': 'B', 'passenger': 33.0, 'cargo': 33.0, 'auto': 34.0} {'name': 'F', 'passenger': 40.0, 'cargo': 50.0, 'auto': 10.0} |