一位邪恶的科学家开发了一种能让鱼产生永不满足的饥饿感的注射剂。注射后，x号的鱼可以吃掉另一条y号较小的鱼(y<x)，并成为x+y号的鱼来保持这种饥饿感。水族馆里有许多大小不一的鱼。这位科学家将一条注射过的鱼引入这个水族馆，目的是最终只剩下一条鱼。为了实现这一点，科学家只允许两种动作：要么添加任何大小的正常鱼类，要么从水族馆中移除现有的正常鱼类。考虑到水族馆中其他鱼类的大小和注射鱼类的大小，编写一个程序来确定科学家实现目标所需的最小移动次数。例如，假设水族馆中有5条鱼，注射的鱼是10号，其他鱼是9、20、25和100号。为了确保水族馆里只剩下1条鱼，科学家需要去掉100号的鱼，再加一条3号的鱼。所以输出是2。步骤顺序如下所示。水族馆中每一步的鱼的大小都用花括号表示。突出显示的数字是注射的鱼的大小。
输入格式：｛infectiedFish｝#｛a，b，c，d…｝其中a、b、c等为正常鱼类的
示例：
- 10#9,25100===>2
- 3#25,20100400500===>5
- 50#25,20,9100===>0
我使用了以下代码来解决这个问题。
public static int count(int inf, int a[], int i, int op){
//base case
if(i==a.length){
return op;
}
while(i<a.length && inf>a[i]){
inf+=a[i];
i++;
}
if(i==a.length){
return op;
}
int curr = inf+inf-1;
return Math.min(count(curr, a, i, op+1), count(inf, a, i+1, op+1));
}
调用它using，System.out.println(count(x, a, 0, 0));x是受感染的鱼，a是给定的排序数组；
这种方法正确吗？如果是这样的话，它似乎有一个共同的子问题，我们如何做记忆？
您可以通过稍微修改算法来提高效率。
如果你有不止一条鱼要吃，最好去掉下一条鱼，然后试着吃一条更大的鱼。
当你吃一条鱼时，你会变得更大，而不需要任何代价。
因此，替代方案是：
- 长大后吃下一条鱼，即添加新鱼后
- 除掉所有剩下的鱼
然后，公式可以简化如下，其他代码保持不变：
return Math.min(count(curr, a, i, op+1), op + a.length -1 - i);
在这种情况下，您不需要记忆：count函数只遵循一种方式，总是增加其内部值。
注意：我假设这里的鱼是排序的，正如您的代码中提到的那样。
复杂性，不考虑排序：O(n + log(weight_max/weigth_in))
编辑：还有另一种方法可以加快这个过程：
如果在给定时间，操作次数op大于当前最佳值，则可以停止递归。
正如其他人所回答的，贪婪可以在这里工作。在第一次吃完所有较小的鱼后，每个选择点都是(1)添加尽可能大的比当前饥饿的鱼小的鱼，或者(2)删除所有相等或较大的鱼。显然，从中间去掉一条鱼是没有必要的，因为如果我们能吃一条更大的，我们也可以吃那条。
我们想要优化的状态是num_current_moves + num_removals_needed。但是，由于我们只需要一个变量来存储最佳状态，我们可以在每次选择后更新它，迭代排序列表，贪婪地添加鱼。选择(2)不是一个积极的变化；相反，它只是计算每个点的最佳视觉状态的一部分。
迭代JavaScript代码：
function f(x, A){
A.sort((a, b) => a - b)
let sum = x
let removals_needed = A.length
let moves = 0
let best = removals_needed
let i = 0
while (i < A.length){
if (sum > A[i]){
sum = sum + A[i]
removals_needed = removals_needed - 1
i = i + 1
// It might not be worth
// trying to grow the fish,
// but the growth rate is
// probably fast enough not
// to add significant time
} else {
sum = sum + (sum - 1)
moves = moves + 1
}
best = Math.min(best, moves + removals_needed)
}
return best
}
var inputs = [
[10, [9,20,25,100]], // 2
[3, [25,20,100,400,500]], // 5
[3, [20,21,22,23,24,25]], // 4
[3, [20,21,22]], // 3
[50, [25,20,9,100]] // 0
]
for (let [x, A] of inputs){
console.log(`${x} -> ${A}`)
console.log(f(x, A))
console.log("")
}让我们总结一下：
有两种可能的干预措施：
移除最大的鱼，以及添加一条比受感染的鱼稍小的鱼。
受感染的鱼可以吞噬所有较小的鱼，每次都会随着被吃掉的鱼的大小而增长。
你希望干预的次数最少，只留下吞噬者。
一个简单得多的算法是：
- 按大小对所有正常鱼类进行排序
- 琐碎的解决方案是手动移除所有鱼类
- 你还没有添加任何新的鱼
- 尽可能长时间地吃掉最小的鱼
- 新的候选解决方案是增加的鱼加上剩余的鱼。选择更好的
- 如果没有鱼了，你就完了
- 根据需要经常添加一条1号大小的鱼来吞食最小的鱼，使吞食者长到2*1号大小
- Contine第4步，吞食鱼类
我将对此解决方案进行两项更改：1.)因为我在问题中没有看到杀手鱼的大小不能为0。或者尺寸为1。我将添加该条件以避免可能的无限循环。
2.)您计算的是递归次数=增加鱼的大小(SI)+移除鱼的次数(RF)。我看不出SI与N或有什么关系
例如
N=100000=10^6
A=[10^7，10^5+10^7，10%6+10^8，…….//对于实际大尺寸的示例
如果受感染的鱼是2号。它下一个可能吃的鱼是10000000条鱼。鱼类总数为10^6。
现在，SI将在2、3、5、8……K等上递归。K>10000000
只是为了看看成本/计数是多少，使其实际上比下一种可能的候选鱼类更大。
所以我不会用递归来计算。我会简单地使用这个逻辑
成本或计数=上限{Ln[(F-1)/(K-1)]}//O(1)
//F=鱼的重量大于受感染的鱼——在递归时。
//K-受感染的鱼目前的体重。
//Ln-登录到基座2。
//天花板将为我们提供四舍五入值，例如天花板(3.4)=4，天花板(3.7)=4。
如果不包括排序成本的话，现在运行成本就是简单的O(n)。
public static int HungryFish(int infectedFishSize, int[] fishs)
{
Array.Sort(fishs);
int moves = 0;
for (int i = 0; i < fishs.Length; i++)
{
if (fishs[i] < infectedFishSize)
{
infectedFishSize += fishs[i];
}
else
{
if (fishs[i] < (infectedFishSize + infectedFishSize - 1))
{
infectedFishSize += (infectedFishSize - 1);
moves++;
}
else
{
moves += (fishs.Length - i);
break;
}
}
}
return moves;
}