组合算法帮助 [英] Combination Algorithm Help
问题描述
所以，我正在创建一个组合算法。以下是挑战细节：您需要创建一个程序来接受4个整数输入，表示与鱼的价值相关的点（前三个整数输入代表三种不同的鱼），然后查看总数中可以容纳多少组合（最后一个整数输入表示你可以拥有的鱼点总数）。
输入在控制台程序中会是这样的，
1 //鱼点值
2 //鱼2点值
3 //鱼3点值
2 //总金额有人可以在没有超出限制的情况下获得积分
输出将显示如下，
1 Brown Trout，0 Northern Pike，0黄色小鱼崽
2棕色鳟鱼，0个北派克，0个黄色小鱼崽
0棕色鳟鱼，1个北派克，0个黄色小鱼肉
捕鱼的方法：3
我已经给了一些提示，比如在循环中使用循环和t o使用while循环，但我仍然很新，很困惑。任何提示或可能会使这个程序发生的示例代码？
So, I'm creating a combination algorithm. Here are the challenge details: You need to create a program to accept 4 integer inputs, representing points associated with how much a fish is worth (first three integer inputs representing three different fish) and then see how many combinations can fit into the total amount (last integer input representing the total amount of fish points you can have).
The input would be like this in a console program,
1 // fish point value
2 // fish 2 point value
3 // fish 3 point value
2 // total amount of points somebody can have without exceeding the limit
The output would be displayed like this,
1 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
2 Brown Trout, 0 Northern Pike, 0 Yellow Pickerel
0 Brown Trout, 1 Northern Pike, 0 Yellow Pickerel
Number of ways to catch fish: 3
I've been given some tips like using loops inside of loops and to use a while loop, but I'm still pretty new and confused. Any tips or maybe some sample code that would make this program happen?
推荐答案
我刚才意识到这与众所周知的背包问题非常相似，只有您不需要找到最佳解决方案，只需将它们全部列出： https：//en.wikipedia .org / wiki / Knapsack_problem [ ^ ]。
从本文中，您可以找到已知解决方案的概述。并非所有这些对您都有帮助，因为您需要列出所有不超过最大总价值的解决方案，而不是最佳总价值。无论如何，因为问题被发现是 NP-complete （ https：//en.wikipedia。 org / wiki / NP-completeness [ ^ ]），你无所事事，但尝试所有可能的解决方案，所以你只需要列出它们。
让我们称之为解决方案的数字代表每个物种捕获的鱼数量。因此，您需要填写表示捕获鱼数的整数数组，数字为0到N，并且只选择总点数不超过总量允许最大值的解决方案。
首先，我会发现每个物种捕获的鱼的最大数量，不超过仅捕获此物种的鱼的最大总量。有N种i = 1 ... N，每个物种的最大鱼数将在范围内
种 0 ：[ 0 .. Max species 0 ]
种 1 ：[0 .. Max species 1 ]
...
种 N-1 ：[0 .. Max 物种 N-1 ]
要检查的变体总数不会超过数量
（最大种 0 +1）*（最大种 1 +1）* ...（Max species N-1 +1）。
你可以按某种顺序尝试所有这些组合，就是这样。
-SA
I just realized that this is very similar to the well-known Knapsack problem, only you don't need to find the optimal solution, just need to list them all: https://en.wikipedia.org/wiki/Knapsack_problem[^].
From this article, you can find the overview of known solutions. Not all of them will be helpful for you, because you need to list all solutions not exceeding the maximum total value, not the best one. Anyway, as the problem is found to be NP-complete (https://en.wikipedia.org/wiki/NP-completeness[^]), you have nothing to do but try all possible solutions, so you just need to list them.
Let's call the "solution" the set of numbers representing the number of caught fish of each species. So, you need to fill in the array of integers representing the number of caught fish with numbers 0 to N and choose only the solution with total point amount not exceeding the allowed maximum for total amount.
First, I would find the maximum numbers of caught fish of each species, not exceeding the maximum total amount in the case you catch fish of only this species. Having N species i = 1... N, your maximum fish numbers for each species will be inside the ranges
species0: [ 0.. Maxspecies0 ]
species1: [ 0.. Maxspecies1 ]
...
speciesN-1: [ 0.. MaxspeciesN−1 ]
The total number of variants to check up won't exceed the number
(Maxspecies0+1) * (Maxspecies1+1) *... (MaxspeciesN−1+1).
You can try all those combinations in some order, that's it.
—SA
这篇关于组合算法帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
