Проблема с вашим кодом заключается в том, что 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;
}