АлгосыЛаба1 - Задача

package main

import (
    "fmt"
)

func last[T interface{}](array []T) T {
    return array[len(array)-1]
}

func countMaxProfit(X0 int, profits [][]int) (int, []int) {
    orgsAmount := len(profits)                        // Кол-во орг
    moneyVariantsAmount := (X0 / 40) + 1              // Кол-во распределения денег (от 0 до 6 (т.е. от 0 до 200 млн))
    dp := make([][]int, orgsAmount+1)                 // Табличка самых выгодных вложений (табличка ДП)
    allocationsOfMoney := make([][]int, orgsAmount+1) // А это сколько какой орге денег давали

    // Выделяем память
    for i := 0; i < orgsAmount+1; i++ {
        dp[i] = make([]int, moneyVariantsAmount)
        allocationsOfMoney[i] = make([]int, moneyVariantsAmount)
    }

    // Составляем табличку ДП
    for currentOrgIndex := 1; currentOrgIndex <= orgsAmount; currentOrgIndex++ {
        for availableMoney := 0; availableMoney < moneyVariantsAmount; availableMoney++ {
            bestSum := 0
            bestAllocation := 0
            for currentMoneyForThisOrg := 0; currentMoneyForThisOrg <= availableMoney; currentMoneyForThisOrg++ {
                currentProfit := dp[currentOrgIndex-1][availableMoney-currentMoneyForThisOrg] + profits[currentOrgIndex-1][currentMoneyForThisOrg]
                if currentProfit > bestSum {
                    bestSum = currentProfit
                    bestAllocation = currentMoneyForThisOrg
                }
            }
            dp[currentOrgIndex][availableMoney] = bestSum
            allocationsOfMoney[currentOrgIndex][availableMoney] = bestAllocation
        }
    }

    fmt.Println("Таблица ДП:", dp)

    // Восстанавливаем сколько каждой орге выделили (в условных единицах)
    resultAllocation := make([]int, orgsAmount)
    remainingAmount := 5
    for i := orgsAmount; i > 0; i-- {
        resultAllocation[i-1] = allocationsOfMoney[i][remainingAmount]
        remainingAmount -= allocationsOfMoney[i][remainingAmount]
    }

    // Переводим из условных единиц в млн. руб.
    for i := 0; i < len(resultAllocation); i++ {
        resultAllocation[i] *= 40
    }

    return last(last(dp)), resultAllocation
}

func main() {
    allOurMoney := 200

    profits := [][]int{
        {0, 8, 10, 11, 12, 18}, // f1(x)
        {0, 6, 9, 11, 13, 15},  // f2(x)
        {0, 3, 4, 7, 11, 18},   // f3(x)
        {0, 4, 6, 8, 13, 16},   // f4(x)
    }

    maxIncome, allocation := countMaxProfit(allOurMoney, profits)

    fmt.Printf("Максимальный доход: %d млн. руб.\n", maxIncome)
    fmt.Println("Распределение средств (млн. руб.):", allocation)
}