using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class InvestmentOptimizer
{
    static void Main()
    {
        string inputFilePath = "C:\\Users\\admin\\source\\repos\\InvestmentAllocation\\InvestmentAllocation\\test.txt";
        string outputFilePath = "result.txt";

        // Чтение данных из файла
        var lines = File.ReadAllLines(inputFilePath);
        int numLevels = lines.Length;
        int numEnterprises = lines[0].Split(' ').Length - 1;

        int[,] profits = new int[numLevels, numEnterprises + 1];
        int[] investmentLevels = new int[numLevels];

        for (int i = 0; i < numLevels; i++)
        {
            var values = lines[i].Split(' ').Select(int.Parse).ToArray();
            investmentLevels[i] = values[0];
            for (int j = 0; j < numEnterprises; j++)
            {
                profits[i, j + 1] = values[j + 1];
            }
        }

        int totalInvestment = investmentLevels[numLevels - 1]; // Последнее значение первого столбца

        // Инициализация массива для хранения максимальной прибыли
        int[,] dp = new int[numEnterprises + 1, totalInvestment + 1];
        int[,] investmentTrack = new int[numEnterprises + 1, totalInvestment + 1];

        // Заполнение таблицы динамического программирования
        for (int i = 1; i <= numEnterprises; i++)
        {
            for (int j = 0; j <= totalInvestment; j++)
            {
                for (int k = 0; k < numLevels; k++)
                {
                    if (investmentLevels[k] <= j)
                    {
                        int profit = profits[k, i] + dp[i - 1, j - investmentLevels[k]];
                        if (profit > dp[i, j])
                        {
                            dp[i, j] = profit;
                            investmentTrack[i, j] = investmentLevels[k];
                        }
                    }
                }
            }
        }

        // Восстановление решения
        int remainingInvestment = totalInvestment;
        var allocation = new int[numEnterprises + 1];

        for (int i = numEnterprises; i > 0; i--)
        {
            allocation[i] = investmentTrack[i, remainingInvestment];
            remainingInvestment -= allocation[i];
        }

        int maxProfit = dp[numEnterprises, totalInvestment];

        // Запись результата в файл
        using (var writer = new StreamWriter(outputFilePath))
        {
            writer.WriteLine($"Итак, инвестиции в размере {totalInvestment} необходимо распределить следующим образом:");
            for (int i = 1; i <= numEnterprises; i++)
            {
                writer.WriteLine($"{i}-му предприятию выделить {allocation[i]}");
            }
            writer.WriteLine($"Максимальная прибыль: {maxProfit}");
        }
    }
}