c# - Knapsack C#实现任务

Question

我正在尝试编写具有给定条件的背包 c# 算法，但我总是遇到两个问题。我收到“索引超出数组范围”错误或我的结果仅为 0。

我找到了几个 Knapsack 实现的代码示例，但无法弄清楚我做错了什么。

代码示例: https://www.programmingalgorithms.com/algorithm/knapsack-problem

http://www.csharpstar.com/csharp-knapsack-problem/

我的代码:

static int Knapsack(int n, int w, int[] s, int[] v)
{
    int[,] G = new int[n+1,w+1];
    for (int k = 0; k <= n; k++)
    {
        for (int r = 0; r < w; r++)
        {
            if (r == 0 || k == 0)
                G[k, r] = 0;
            else if (s[k] <= r)
                G[k, r] = Math.Max(G[k- 1, r], v[k] + G[k - 1, r - s[k]]);
            else
                G[k, r] = G[k - 1, r]; 
        }
    }
    return G[n, w];
}
static void Main(string[] args)
{
    int[] s = { 60, 100, 120};
    int[] v = { 10, 20, 30 };
    int w = 50;
    int n = s.Length;
    Console.WriteLine(Knapsack(n, w, s, v));
}

在这种情况下，我的结果是 0。

Answer 1

您的代码的问题是 s 是权重，v 是值，您的权重 60、100 和 120 显然不适合容量50，这就是你得到 0 结果的原因。你从集合中提取这些值的示例是 60、100 和 120 作为值，10、20 和 30 作为权重，这就是它得到 220 结果的原因。

我认为如果您创建一个类来处理元素的相关重量和值(value)，效果会更好。

public class Item
{
    public int Weight { get; set; }
    public int Value { get; set; }
}

然后该方法只需要一个项目数组和所需的容量。此外，使用有意义的名称比一堆单字母名称更容易理解正在发生的事情。

public static int KnapSack(Item[] items, int capacity)
{
    int[,] matrix = new int[items.Length + 1, capacity + 1];
    for (int itemIndex = 0; itemIndex <= items.Length; itemIndex++)
    {
        // This adjusts the itemIndex to be 1 based instead of 0 based
        // and in this case 0 is the initial state before an item is
        // considered for the knapsack.
        var currentItem = itemIndex == 0 ? null : items[itemIndex - 1];
        for (int currentCapacity = 0; currentCapacity <= capacity; currentCapacity++)
        {
            // Set the first row and column of the matrix to all zeros
            // This is the state before any items are added and when the
            // potential capacity is zero the value would also be zero.
            if (currentItem == null || currentCapacity == 0)
            {
                matrix[itemIndex, currentCapacity] = 0;
            }
            // If the current items weight is less than the current capacity
            // then we should see if adding this item to the knapsack 
            // results in a greater value than what was determined for
            // the previous item at this potential capacity.
            else if (currentItem.Weight <= currentCapacity)
            {
                matrix[itemIndex, currentCapacity] = Math.Max(
                    currentItem.Value 
                        + matrix[itemIndex - 1, currentCapacity - currentItem.Weight],
                    matrix[itemIndex - 1, currentCapacity]);
            }
            // current item will not fit so just set the value to the 
            // what it was after handling the previous item.
            else
            {
                matrix[itemIndex, currentCapacity] = 
                    matrix[itemIndex - 1, currentCapacity];
            }
        }
    }

    // The solution should be the value determined after considering all
    // items at all the intermediate potential capacities.
    return matrix[items.Length, capacity];
}

然后运行这段代码

var items = new[]
{
    new Item {Value = 60, Weight = 10},
    new Item {Value = 100, Weight = 20},
    new Item {Value = 120, Weight = 30},
};

Console.WriteLine(KnapSack(items, 50));

结果为 220。

这是一个使用递归的解决方案。

public static int KnapSackRecursive(Item[] items, int capacity)
{
    // If there are no items or capacity is 0 then return 0
    if (items.Length == 0 || capacity == 0) return 0;

    // If there is one item and it fits then return it's value
    // otherwise return 0
    if (items.Length == 1)
    {
        return items[0].Weight < capacity ? items[0].Value : 0;
    }

    // keep track of the best value seen.
    int best = 0;
    for (int i = 0; i < items.Length; i++)
    {
        // This is an array of the other items.
        var otherItems = items.Take(i).Concat(items.Skip(i + 1)).ToArray();

        // Calculate the best value without using the current item.
        int without = KnapSackRecursive(otherItems, capacity);
        int with = 0;

        // If the current item fits then calculate the best value for
        // a capacity less it's weight and with it removed from contention
        // and add the current items value to that.
        if (items[i].Weight <= capacity)
        {
            with = KnapSackRecursive(otherItems, capacity - items[i].Weight) 
                + items[i].Value;
        }

        // The current best is the max of the with or without.
        int currentBest = Math.Max(without, with);

        // determine if the current best is the overall best.
        if (currentBest > best)
            best = currentBest;
    }

    return best;
}