.NET 4.x Задача о рюкзаке методом динамического программирования, исправить код - 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();
        }
    }
}
В методе Print есть закомментированный кусок, по идее он рабочий. Проблема в том, что в итоговом массиве одни нули... Я делал по примеру на паскале, что нашел в инете:
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.
Пример рабочий, проверял. Но мне пришлось сделать видоизменения на C# т.к. индексы выходили за пределы массива в циклах, где написано про реализацию алгоритма Беллмана, а также в строке
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;

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


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

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

10   голосов , оценка 3.7 из 5
Похожие ответы