背包C＃实施任务 [英] Knapsack C# implementation task

问题描述

我正在尝试在给定条件下编写背包式C＃算法，但始终遇到两个问题。我收到索引超出数组范围错误或我的结果仅为0。

I'm trying to write knapsack c# algorithm with given conditions but there's always two problems i encountering. I'm getting "Index was outside the bounds of the array" error or my result is just 0.

我发现了Knapsack实现的几个代码示例，但无法找出我在做什么错。

I found couple code examples of Knapsack implementation and just can't figure out what I'm doing wrong.

代码示例：
https://www.programmingalgorithms.com/algorithm/knapsack问题

> 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。

In this case my result is 0.

推荐答案

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

The issue with your code is that s is the weights and v is the values and your weights of 60, 100, and 120 will obvious not fit into a capacity of 50, that's why you get a result of 0. The example you pull those values from set's the 60, 100, and 120 as the values and 10, 20, and 30 as the weights which is why it gets a result of 220.

我认为如果创建一个

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

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

Then the method only needs an array of items and the desired capacity. Also using meaningful names can make understanding what's going on easier than a bunch of single letter names.

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。

这里是a

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

这篇关于背包C＃实施任务的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！