Приветствую всех, сегодня рассмотрим алгоритм решения задачи «Рюкзак».
По условию задания у нас есть набор предметов. У каждого предмета есть вес и цена. Нужно собрать рюкзак, уложившись в предел веса(40 кг) и обеспечив максимальную стоимость содержимого.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Knapsack { class KnapsackAlgorithm { public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount) { int[,] K = new int[itemsCount + 1, capacity + 1]; for (int i = 0; i <= itemsCount; ++i) { for (int w = 0; w <= capacity; ++w) { if (i == 0 || w == 0) K[i, w] = 0; else if (weight[i - 1] <= w) K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]); else K[i, w] = K[i - 1, w]; } } return K[itemsCount, capacity]; } static void Main(string[] args) { int[] value = { 10, 50, 70 }; int[] weight = { 10, 20, 30 }; int capacity = 40; int itemsCount = 3; int result = KnapSack(capacity, weight, value, itemsCount); Console.WriteLine(result); Console.ReadKey(); } } } |