.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;