我对复杂算法非常陌生(直到现在都在做简单的程序)，并且我正在尝试开发一个程序，用户可以在其中输入所需的预算，并且该程序将搜索用户可以从每种产品中购买的最佳产品。类别。
例子:
产品:
衬衫:
衬衫A-$ 20
衬衫B-15美元
衬衫C-10美元
裤子:
裤子A-$ 30
B裤子-$ 25
C裤子-$ 20
鞋:
鞋子A-$ 20
鞋子B-$ 15
shoesC-10美元
用户输入(预算):60美元
输出:
衬衫B-15美元
裤子A-$ 30
鞋子B-$ 15
总计:$ 60
...或类似的东西。我应该研究哪种算法？我觉得很难，因为我不知道从哪里开始了解要使用哪种算法。瞧，这是类的，我们的教授希望我们指出我们使用了哪种算法。我想，如果我只是蛮力尝试并犯错，我实际上可以完成此操作，但是那时我不知道我使用了哪种算法。无论如何，谢谢大家。
最佳答案
问题是Knapsack problem的变体；与其选择是否要在解决方案中包含某个项目，还必须从每个类别中选择要提取的项目。尽管未在Wikipedia文章中明确说明，但可以通过修改基本表述的Dynamic programming来在通过recurrence relation绑定(bind)的伪多项式运行时中解决问题中的表述。
关于algorithm - 我应该使用哪种算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31431712/