.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;
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д