我假设您在开始算法时已经知道了所有给出的数字,并且在完成t1后不会得到t2等。
我还假设两个弹弓可以同时发射,虽然这不应该有太大影响。
在第一个选择时,您可以为每个单元格分配一个值,即amountOfBirdsInCell-time。
这给您带来了两个值为1的单元格,即S1t1、S1t2,其余单元格的值较低。
只有最后一个单元格的时间对您的得分有影响,因此选择最早的单元格将为下一轮删除其上的时间,使其成为最有价值的时间。这是第一个选择。
现在,从所有单元格中删除那个第一个选择中杀死的鸟。
重复剩余单元格的值确定过程。在您的示例中,单元格S3t2将给出最高结果,即0。
重复此过程,您将获得最早时间的最有价值的单元格。
您的示例没有涵盖的一个重要部分:如果您的第一个最有价值的选择是在t2,那么下一个最有价值的选择可能在t1或t2,因此您应该考虑它们。但是,由于t2已经确认,您不应该考虑它们的时间对其价值的影响。
我从未写过Python,只是因为算法标签而来,所以这里是一些类似于Java/C的伪代码:
highestCellTime = 0;
while(birdsRemain)
{
bestCell;
for(every cell that has not been picked yet)
{
currentCellValue = amountOfBirds;
if(currentCellTime > highestCellTime)
{
currentCellValue = currentCellValue - currentCellTime;
}
if(currentCellValue < bestCellValue)
{
bestCell = thisCell;
}
else if(currentCellValue == bestCellValue && currentCellTime < bestCellTime)
{
bestCell = thisCell;
}
}
addCellToPicks(bestCell);
removeBirdsFromOtherCells(bestCellBirds);
}
除非我忘了什么,否则您现在在选择集合中拥有最佳单元的组合。
我希望这段代码对Python程序员有意义。如果有人能翻译一下,请务必这样做!当您这样做时,请删除此文本和早期提到的Java / C伪代码。
编辑者注:这是第一个版本,没有得到最好的单元。我猜这一定是我的代码中的错误,但无论如何我都会在这里发布。
import math
cellsNotPicked = range(0,12)
cellToBird = {
0: [1, 2],
1: [],
2: [1],
3: [1,2,3],
4: [1],
5: [3,4],
6: [4],
7: [1,2],
8: [],
9: [],
10: [3,4],
11: [1,2,3,4]
}
picks = []
def getCellValue(cell):
return len(cellToBird[cell])
def getCellTime(cell):
return int(math.floor(cell / 3)) + 1
birdsRemain = 4
while(birdsRemain > 0):
bestCell = 0;
for thisCell in cellsNotPicked:
currentCellValue = getCellValue(thisCell);
currentCellTime = getCellTime(thisCell)
highestCellTime = getCellTime(bestCell)
if(currentCellTime > highestCellTime):
currentCellValue = currentCellValue - currentCellTime;
if(currentCellValue < getCellValue(bestCell)):
bestCell = thisCell
elif (currentCellValue == getCellValue(bestCell)) and (currentCellTime < getCellTime(bestCell)):
bestCell = thisCell
picks.append(bestCell)
cellsNotPicked.remove(bestCell)
birdsToRemove = cellToBird[bestCell]
for key in cellToBird:
for bird in birdsToRemove:
try:
cellToBird[key].remove(bird)
birdsRemain -= 1
except:
pass
print picks