好的，示例无关紧要。我只是用它来把它放在上下文中。但基本上我想知道如何从数组/数组列表中获取随机值？
我尝试使用它：int random = (int)input[Math.floor(Math.random() * input.length)];
但它突出了潜在的精度损失，即使我已经cast这样做了。我投错了吗？
这个例子真的无关紧要，我接受我所有问题的答案。最初我想在不受我影响的情况下看到一个正确的答案，看看我是否走在正确的轨道上。
问问题
82 次
1 回答
1
这正是装箱问题。它也是NP-Complete，因此没有已知的多项式解决方案（一般假设是不存在，但尚未证明）。
如果您正在寻找近似算法或相对有效的精确算法，则该问题被广泛研究
PS - 你建议的随机方法会给你一个解决方案，但它不会是最优的。
反例：
arr = [2,3,4,1] , size=5
您的算法的可能解决方案可能是：select 3, select 1, select 4, select 2，这将产生：
[3,1],[4],[2]
虽然最佳解决方案将是[3,2],[4,1]
（-）我相信贪婪的方法（选择最高的，把它放在一个可用的箱子里——如果合适，如果不合适——“打开”一个新的箱子）会比随机解决方案做得更好，但仍然不会最优，反例：
arr = [5,4,4,3,2,2] size = 10
贪婪会产生[5,4],[4,3,2],[2]，而最优是[5,3,2],[4,4,2]
关于损失 pf 精度- 发生这种情况是因为Math.floor(double)产生 a long，而您将其用作 a int（理论上这样做时您可能会丢失数据）。但是，在您的情况下这不是问题，因为Math.floor(Math.random() * input.length保证在 an 范围内，int因为input.length是 int 和Math.random() < 1。
于 2012-11-29T11:44:22.103 回答