这是一个创建于 1351 天前的主题，其中的信息可能已经有所发展或是发生改变。
每个装备只能选一个属性，即一行只能有一个属性。
每列可以有多个属性，也可以没有属性。
每列上的数据先相加。
每列相加之和各自加底数 1 之后再相乘。
求最终最大值。 [穷举太慢，自己写的逻辑算出来 2.139 ，还不到最大]
第 1 条附言 · 2021-04-12 14:40:51 +08:00
 |
1
linvon 2021-04-12 11:15:08 +08:00
这都 2021 年了，DNF 的计算器应该一大堆了吧，还用自己写？
|
 |
2
andersonGzy OP @linvon 单纯的想知道，怎么解方便。。。
|
 |
3
no1xsyzy 2021-04-12 11:22:29 +08:00
直觉上是个离散凸包优化，随机化算法会比较好
用启发式爬坡算法 先预设一个初始选择。 第一层死循环；第二层循环每件装备，尝试重选；如果某轮循环中重新选取后不发生改变，则认为最优 但可能实际上有局部最优，可以随机生成若干个初始选择，或者用把爬坡改退火 …… 但我想了想，6**8 也不过 167 万，太慢是不是干了什么诡异的或者多余的操作？ |
 |
4
kalluwa 2021-04-12 11:47:07 +08:00
brute force 一下就算出来：2.34208
ms 级别的计算量 |
 |
5
zyx199199 2021-04-12 11:48:10 +08:00  1
整数线性规划求解。
8 个装备定为 1-8 号。六种属性分别定为 a,b,c,d,e,f,。然后将他们组合，得到 a1, a2,...,b1, b2,...,f8，一共 48 个变量 每个变量值只能取 0 或 1 例如，用 a1 这个变量表示装备 1 是否选择 “力智” 这个属性。a1=1 表示装备 1 选择力智属性，a1=0 表示装备 1 不选择力智属性。 最终求解的就是 （ a1*0.169 + a2*0.085+...+...+a8*0 + 1 ）*...*（ f1*0.186+...+f8*0+1 ） 的最大值。不过要满足一行最多只能选一个属性的条件，即 a1+b1+c1+...+g1 <=1 a2+b2+c2+...+g2 <= 1 ... a8+b8+...+g8 <=1 这种规模的数据，excel 就能解 |
 |
6
tabris17 2021-04-12 11:52:23 +08:00
线性规划问题，踩石法，我得把课本找出来看看了
|
 |
7
imn1 2021-04-12 13:18:34 +08:00
8 行 6 列，一定有同一列重复的，重复的规则是什么？
装备 7 为何不选 0.057 ，装备 8 为何不选 0.032 ？ |
|
8
andersonGzy OP @no1xsyzy 哈哈哈，我草率了，我最开始想着 2*8*6 就出结果了。
|
|
9
andersonGzy OP @kalluwa 直觉上暴力不是最慢的吗。大佬要不发下代码。
|
|
10
andersonGzy OP @zyx199199 主要是想用代码，活动活动我的小脑袋，就当它规模大吧。。。
|
|
11
andersonGzy OP @imn1 规则写了啊，至于为什么不选，图中下面的只是别人乱点的数据，是范例。
|
|
12
imn1 2021-04-12 14:01:56 +08:00
|
|
13
andersonGzy OP @imn1 允许的。你这么只有 1.032 * 1.815 = 1.87308，老小了。
|
|
14
imn1 2021-04-12 14:19:13 +08:00
@andersonGzy #13
不对，是 2.x * 1.032 ，要加底数 1，除非你还有规则说明合计超过 1 时不加底数 |
|
15
imn1 2021-04-12 14:21:21 +08:00
@andersonGzy #13
呃，好像是我摁错计算器了……尴尬 |
 |
16
xuegy 2021-04-12 14:31:40 +08:00 via iPhone
投机取巧的办法
(1+a+b)=(1+a)*(1+b)-a*b，数都不大的所以先忽略 a*b 所以全+1，直接算乘积最大，为求保险，可以取最大前 10 项，然后再从候选的里面算一遍真实的。 |
|
17
andersonGzy OP @xuegy 投不出来
|
 |
18
Marine5174 2021-04-12 17:14:16 +08:00
将这个矩阵理解为一个(M,N)的完全二分图的边的权重,问题即为求该二分图的最大匹配.
|
 |
19
timsensor 2021-04-12 19:30:54 +08:00
excel 或者 wps 可以做规划求解
|
 |
20
leewangyang 2021-04-12 23:00:55 +08:00 via Android
可以当作二部图带权匹配问题吧，如果是简单加法有 KN 算法。但是如果还要+1 算乘积，可能得改改。
|
 |
21
xml123 2021-04-13 00:18:38 +08:00
怎么我算出来的最大只有 2.145
选的分别是 2, 1, 4, 6, 5, 4, 4, 5 |
 |
22
proxychains 2021-04-13 06:54:59 +08:00
dnf 玩家...
|
|
23
andersonGzy OP @timsensor 朋友，几万件装备也用 Excel 吗 - -。
|
 |
24
aptx4689 2021-04-13 10:43:28 +08:00
|
|
25
andersonGzy OP @aptx4689 em...就是要改这个东西，它就是问题的起源。
|
 |
26
fcxxzux 2021-04-13 14:57:48 +08:00
就按照 zyx199199 写的思路，然后找个求解器来算最优解就行。
比如，Google OR-Tools https://developers.google.com/optimization/cp/integer_opt_cp 或者 Z3 https://github.com/Z3Prover/z3/blob/master/examples/python/tutorial/jupyter/guide.ipynb （声明：没用过 Z3，用过 Google OR-Tools 解 500*50 个 0/1 变量和一堆复杂条件结合的问题，开了 8 个 worker ~40 秒） |
|
27
andersonGzy OP |
Select Language