列表中的最大数小于数

-3

如果我有一个数字列表，我该如何快速找到比另一个数小的最大数。例如，在{40,60,22,15,51,22,5,55,32,70}列表中，最大的总和小于50.感谢您的帮助，因为我能找到的唯一解决方案是递归，这似乎效率低下。这是一个我在当时无法解决的比赛问题，自那以来一直让我感到沮丧。列表中的最大数小于数

来源

2017-07-31 tristan wiesepape

我建议你关闭你的电脑。拿一张纸和一支铅笔。然后写下解决问题所需的步骤。想想如果有人给你一个数字列表，你会怎么做。 –

“，因为我能找到的唯一解决方案是递归的，这看起来效率很低”不要担心效率。在担心性能之前编写一个能够提供正确解决方案的程序非常重要。 –

我递归解决了它，但我正在寻找更快的东西 –

这相当于背包问题，它是动态规划中的一个着名问题。这样想吧：你是个小偷，你想尽可能地偷。你的背包有固定的尺寸，你只能拿那么多。有一个项目列表，他们每个都有一定的价值和规模。你想最大限度地提高被盗的价值。选择哪些物品可以挑选哪些不是最佳的方式是什么？所以在你的情况下，50是背包的大小，数字是项目（这里value = size）。

希望这有助于！

来源

2017-07-31 03:44:11 Mvteja

列表中的最大数小于数

回答

相关问题