.NET 4.x Задача о рюкзаке методом динамического программирования, исправить код - C#

Узнай цену своей работы

Формулировка задачи:

Помогите разобраться! Написал прогу, которая должна решать задачу о рюкзаке методом Беллмана (динамическое программирование), однако она не работает...
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace ryukzak
  7. {
  8. class Article //товар
  9. {
  10. public string name; //название товара
  11. public int weight; //вес товара
  12. public int price; //цена товара
  13. public Article(string n, int w, int p)
  14. {
  15. name = n;
  16. weight = w;
  17. price = p;
  18. }
  19. }
  20. class Program
  21. {
  22. public static Article[] articles;
  23. public static int numsArticle; // Количество товаров
  24. public static bool incorrEnter; //Переменная, что проверяет корректность ввода
  25. public static string name; // Имя товара
  26. public static int weight, price, maxWeight; // Вес и цена товара, размер рюкзака
  27. public static int[,] func; //массив для хранения значений функции
  28. // Метод выводит на экран рюкзак
  29. static void Print(int s, int n)
  30. {
  31. foreach (int x in func)
  32. Console.Write(x + " ");
  33. /*if (func[s, n] != 0)
  34. if (func[s - 1, n] == func[s, n])
  35. Print(s - 1, n);
  36. else
  37. {
  38. Print(s - 1, n - articles[s].weight);
  39. Console.WriteLine(s);
  40. }*/
  41. }
  42. static void Main(string[] args)
  43. {
  44. int s, n; //просто переменные :)
  45. Console.WriteLine("Данная программа поможет Вам заполнить Ваш рюкзак максимально ценными товарами\nАвтор: Владимир Рыбалка");
  46. //Введем количество товаров
  47. do
  48. {
  49. incorrEnter = false;
  50. Console.Write("\nКакое количество товаров вы рассматриваете для приобретения: ");
  51. try
  52. {
  53. numsArticle = Convert.ToInt32(Console.ReadLine());
  54. }
  55. catch(FormatException)
  56. {
  57. incorrEnter = true;
  58. numsArticle = 0;
  59. }
  60. } while (incorrEnter);
  61. articles = new Article[numsArticle]; //Создаем массив заданного размера
  62. //Создадим объекты товаров
  63. for (int i = 0; i < articles.Length; i++)
  64. {
  65. Console.Write("\n\nВведите название " + i+1 + "-го товара: ");
  66. name = Console.ReadLine();
  67. do
  68. {
  69. incorrEnter = false;
  70. Console.Write("Введите вес товара: ");
  71. try
  72. {
  73. weight = Convert.ToInt32(Console.ReadLine());
  74. }
  75. catch (FormatException)
  76. {
  77. incorrEnter = true;
  78. weight = 0;
  79. }
  80. } while (incorrEnter);
  81. do
  82. {
  83. incorrEnter = false;
  84. Console.Write("Введите цену товара: ");
  85. try
  86. {
  87. price = Convert.ToInt32(Console.ReadLine());
  88. }
  89. catch (FormatException)
  90. {
  91. incorrEnter = true;
  92. price = 0;
  93. }
  94. } while (incorrEnter);
  95. articles[i] = new Article(name, weight, price); //Создаем объект
  96. }
  97. // Введем размер рюкзака
  98. do
  99. {
  100. incorrEnter = false;
  101. Console.Write("\nВведите размер вашего рюкзака (контейнера): ");
  102. try
  103. {
  104. maxWeight = Convert.ToInt32(Console.ReadLine());
  105. }
  106. catch (FormatException)
  107. {
  108. incorrEnter = true;
  109. maxWeight = 0;
  110. }
  111. } while (incorrEnter);
  112. func = new int[numsArticle, maxWeight]; //Реализуем массив функции
  113. //Реализуем алгоритм Беллмана
  114. for (n = 0; n < maxWeight; n++)
  115. func[0, n] = 0;
  116. for (s = 1; s < numsArticle; s++)
  117. for (n = 0; n < maxWeight; n++)
  118. {
  119. func[s, n] = func[s - 1, n];
  120. if ((n >= articles[s].weight) && ((func[s - 1, n - articles[s].weight] + articles[s].price) > func[s, n]) && (n - articles[s].weight + articles[s].price < maxWeight))
  121. func[s, n] = func[s - 1, n - articles[s].weight + articles[s].price];
  122. }
  123. Print(numsArticle, maxWeight);
  124. Console.ReadKey();
  125. }
  126. }
  127. }
В методе Print есть закомментированный кусок, по идее он рабочий. Проблема в том, что в итоговом массиве одни нули... Я делал по примеру на паскале, что нашел в инете:
Листинг программы
  1. const k=5; ww=15;
  2. w:array [1..k] of integer=(6,4,3,2,5);
  3. p:array [1..k] of integer=(5,3,1,3,6);
  4. var a:array [0..k,0..ww] of integer;
  5. s,n:integer;
  6. procedure Print(s,n:integer);
  7. begin
  8. if (A[s,n]<>0) then
  9. if (A[s-1,n] = A[s,n])
  10. then Print(s-1,n)
  11. else begin
  12. Print(s-1,n-w[s]);
  13. writeln(s);
  14. end;
  15. end;
  16. begin
  17. for n:=0 to ww do A[0,n]:=0;
  18. for s:=1 to k do
  19. for n:=0 to ww do
  20. begin
  21. A[s,n]:=A[s-1,n];
  22. if (n>=w[s]) and (A[s-1,n-w[s]]+p[s] > A[s,n])
  23. then A[s,n]:= A[s-1][n-w[s]]+p[s];
  24. end;
  25. print(k,ww);
  26. end.
Пример рабочий, проверял. Но мне пришлось сделать видоизменения на C# т.к. индексы выходили за пределы массива в циклах, где написано про реализацию алгоритма Беллмана, а также в строке
Листинг программы
  1. if ((n >= articles[s].weight) && ((func[s - 1, n - articles[s].weight] + articles[s].price) > func[s, n]) && (n - articles[s].weight + articles[s].price < maxWeight))
пришлось добавить третье условие:
Листинг программы
  1. (n - articles[s].weight + articles[s].price < maxWeight)
т.к. второй индекс присваиваемого значения превышал за пределы массива. Я уже голову сломал. Подскажите, буду очень признателен!

Решение задачи: «.NET 4.x Задача о рюкзаке методом динамического программирования, исправить код»

textual
Листинг программы
  1. articles[i].take = false;

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 3.7 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы