背包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的结果的原因.

我认为如果你创建一个类来处理项目的相关权重和值,这会更好.

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;
}