如何使用 C# 代码重写这个背包 JavaScript 函数?

分享于2022年07月17日 c# 问答
【问题标题】:如何使用 C# 代码重写这个背包 JavaScript 函数?(How to rewrite this knapsack javascript function using C# code?)
【发布时间】:2022-07-13 21:13:45
【问题描述】:

我正在尝试使用 c# 代码重写此 question 的答案。由于 C# 尚未普及,而且我们会出现超出范围的异常,因此这是一项艰巨的任务。我设法编写了以下代码,它可以工作,但我相信有更好的方法来做到这一点。

 int? result = MaxCollectableTreasure(new List() {1, 3, 1, 8, 7 }, 3);
    
    int? MaxCollectableTreasure(List chests, int minutes)
    {
        if (chests.Count == 1 && minutes > 0)
            return chests[0];
    
        int? firstElement = chests[0];
        var restOfList = chests.Skip(1).Take(chests.Count).ToList();
    
        return MaxCollectableTreasuresRecursive(firstElement, restOfList, minutes);
    }
    
    int? MaxCollectableTreasuresRecursive(int? firstElement, List chests, int minutes)
    { 
        if (minutes == 0 || firstElement is null)
            return 0;
    
        if (firstElement == 0)
            return MaxCollectableTreasuresRecursive(chests.FirstOrDefault(), AllButFirst(chests), minutes - 1);
    
        var left = firstElement + MaxCollectableTreasuresRecursive(0, AllButFirst(chests.Prepend(0)), minutes - 1);
        var right = MaxCollectableTreasuresRecursive(chests.FirstOrDefault(), AllButFirst(chests), minutes - 1);
    
        int leftAsInt = left ?? 0;
        int rightAsInt = right ?? 0;
    
        return Math.Max(leftAsInt, rightAsInt);
    }
    
    List AllButFirst(IEnumerable chests)
    {
        return chests.Skip(1).Take(chests.Count()).ToList();
    }


【解决方案1】:

这里有一个非常漂亮的实现,可以很快解决问题。

我只能看到您在此处所做的一些性能改进,这会增加执行时间的一小部分。

int? result = MaxCollectableTreasure(new List() { 1, 3, 1, 8, 7 }, 3);

int? MaxCollectableTreasure(IReadOnlyList chests, int minutes)
{
    if (chests.Count == 1 && minutes > 0)
        return chests[0];

    int? firstElement = chests[0];
    var restOfList = chests.Skip(1);

    return MaxCollectableTreasuresRecursive(firstElement, restOfList, minutes);
}

int? MaxCollectableTreasuresRecursive(int? firstElement, IEnumerable chests, int minutes)
{
    while (true)
    {
        if (minutes == 0 || firstElement is null) return 0;

        if (firstElement == 0)
        {
            firstElement = chests.FirstOrDefault();
            chests = chests.Skip(1);
            minutes -= 1;
            continue;
        }

        var left = firstElement + MaxCollectableTreasuresRecursive(0, chests, minutes - 1);
        var right = MaxCollectableTreasuresRecursive(chests.FirstOrDefault(), chests.Skip(1), minutes - 1);

        int leftAsInt = left ?? 0;
        int rightAsInt = right ?? 0;

        return Math.Max(leftAsInt, rightAsInt);
    }
}

首先,您不需要 .Take().ToList() 来获取箱子,只需 .Skip() 自己就可以满足您的需求。

在计算左边的值时,你在胸部前面加上 0,然后在它上面做一个跳过 1,这样就可以去掉它来整理那个位。

但必须说,您已经对 Javascript 等价物做了非常简洁的解释!