.NET 4.x Задача о рюкзаке методом динамического программирования, исправить код - C#
Формулировка задачи:
Помогите разобраться! Написал прогу, которая должна решать задачу о рюкзаке методом Беллмана (динамическое программирование), однако она не работает...
В методе Print есть закомментированный кусок, по идее он рабочий. Проблема в том, что в итоговом массиве одни нули... Я делал по примеру на паскале, что нашел в инете:
Пример рабочий, проверял. Но мне пришлось сделать видоизменения на C# т.к. индексы выходили за пределы массива в циклах, где написано про реализацию алгоритма Беллмана, а также в строке
пришлось добавить третье условие:
т.к. второй индекс присваиваемого значения превышал за пределы массива.
Я уже голову сломал. Подскажите, буду очень признателен!
Листинг программы
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace ryukzak
- {
- class Article //товар
- {
- public string name; //название товара
- public int weight; //вес товара
- public int price; //цена товара
- public Article(string n, int w, int p)
- {
- name = n;
- weight = w;
- price = p;
- }
- }
- class Program
- {
- public static Article[] articles;
- public static int numsArticle; // Количество товаров
- public static bool incorrEnter; //Переменная, что проверяет корректность ввода
- public static string name; // Имя товара
- public static int weight, price, maxWeight; // Вес и цена товара, размер рюкзака
- public static int[,] func; //массив для хранения значений функции
- // Метод выводит на экран рюкзак
- static void Print(int s, int n)
- {
- foreach (int x in func)
- Console.Write(x + " ");
- /*if (func[s, n] != 0)
- if (func[s - 1, n] == func[s, n])
- Print(s - 1, n);
- else
- {
- Print(s - 1, n - articles[s].weight);
- Console.WriteLine(s);
- }*/
- }
- static void Main(string[] args)
- {
- int s, n; //просто переменные :)
- Console.WriteLine("Данная программа поможет Вам заполнить Ваш рюкзак максимально ценными товарами\nАвтор: Владимир Рыбалка");
- //Введем количество товаров
- do
- {
- incorrEnter = false;
- Console.Write("\nКакое количество товаров вы рассматриваете для приобретения: ");
- try
- {
- numsArticle = Convert.ToInt32(Console.ReadLine());
- }
- catch(FormatException)
- {
- incorrEnter = true;
- numsArticle = 0;
- }
- } while (incorrEnter);
- articles = new Article[numsArticle]; //Создаем массив заданного размера
- //Создадим объекты товаров
- for (int i = 0; i < articles.Length; i++)
- {
- Console.Write("\n\nВведите название " + i+1 + "-го товара: ");
- name = Console.ReadLine();
- do
- {
- incorrEnter = false;
- Console.Write("Введите вес товара: ");
- try
- {
- weight = Convert.ToInt32(Console.ReadLine());
- }
- catch (FormatException)
- {
- incorrEnter = true;
- weight = 0;
- }
- } while (incorrEnter);
- do
- {
- incorrEnter = false;
- Console.Write("Введите цену товара: ");
- try
- {
- price = Convert.ToInt32(Console.ReadLine());
- }
- catch (FormatException)
- {
- incorrEnter = true;
- price = 0;
- }
- } while (incorrEnter);
- articles[i] = new Article(name, weight, price); //Создаем объект
- }
- // Введем размер рюкзака
- do
- {
- incorrEnter = false;
- Console.Write("\nВведите размер вашего рюкзака (контейнера): ");
- try
- {
- maxWeight = Convert.ToInt32(Console.ReadLine());
- }
- catch (FormatException)
- {
- incorrEnter = true;
- maxWeight = 0;
- }
- } while (incorrEnter);
- func = new int[numsArticle, maxWeight]; //Реализуем массив функции
- //Реализуем алгоритм Беллмана
- for (n = 0; n < maxWeight; n++)
- func[0, n] = 0;
- for (s = 1; s < numsArticle; s++)
- for (n = 0; n < maxWeight; n++)
- {
- func[s, n] = func[s - 1, n];
- 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))
- func[s, n] = func[s - 1, n - articles[s].weight + articles[s].price];
- }
- Print(numsArticle, maxWeight);
- Console.ReadKey();
- }
- }
- }
Листинг программы
- const k=5; ww=15;
- w:array [1..k] of integer=(6,4,3,2,5);
- p:array [1..k] of integer=(5,3,1,3,6);
- var a:array [0..k,0..ww] of integer;
- s,n:integer;
- procedure Print(s,n:integer);
- begin
- if (A[s,n]<>0) then
- if (A[s-1,n] = A[s,n])
- then Print(s-1,n)
- else begin
- Print(s-1,n-w[s]);
- writeln(s);
- end;
- end;
- begin
- for n:=0 to ww do A[0,n]:=0;
- for s:=1 to k do
- for n:=0 to ww do
- begin
- A[s,n]:=A[s-1,n];
- if (n>=w[s]) and (A[s-1,n-w[s]]+p[s] > A[s,n])
- then A[s,n]:= A[s-1][n-w[s]]+p[s];
- end;
- print(k,ww);
- end.
Листинг программы
- 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))
Листинг программы
- (n - articles[s].weight + articles[s].price < maxWeight)
Решение задачи: «.NET 4.x Задача о рюкзаке методом динамического программирования, исправить код»
textual
Листинг программы
- articles[i].take = false;
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д