Java Рекурсивный Откат

Question

Я изучаю компьютерную науку, и в настоящее время я практикую откат назад, потому что я очень плох в этом. Я нашел это упражнение онлайн:

Вы продаете яблоки. Это текущие таблицы цен на ваши яблоки:

Количество 1 2 3 4 5 6 7 8 Цена 1 5 8 9 10 17 17 20

Так что, если вы продаете 8 яблок одновременно, вы получите 20 $. Если вы продаете 6, а затем 2, вы получите 22 $. Попробуйте найти максимальную прибыль. Вот метод, который вы должны использовать:

public static long sellApples(int count, long[] prices) {

}

Теперь я думал об этом как 5 часов, но не могу найти хорошее решение. Кто-нибудь готов к небольшому испытанию?

Answer 1

надеюсь, это поможет вам.

    public static long sellApples(int count, long[] prices) {
    long maxKnownValue = 0L;
    if(count==1){
        return prices[0];
    }
    for(int i=1;i<=prices.length && i<=count;i++){
        long valueCandidate = sellApples(count-i, prices)+prices[i-1];
        if(valueCandidate>maxKnownValue){
            maxKnownValue=valueCandidate;
        }
    }
    return maxKnownValue;
}

Answer 2

Я не эксперт по этому вопросу, поэтому возьмите то, что я говорю, с крошкой соли.

В этом методе вам нужно разделить счет на куски, например 8 => 3, 5.Вам нужно снова вызвать этот метод, оба значения которого равны count.Это наиболее очевидная часть.

Хитрость в том, что вам нужно признать, что достаточно разделить счет на 2 части.Я имею в виду, что вам не нужно пытаться вызывать метод со значениями 1,2,5, потому что если вы просто вызовете его с помощью 3,5, то следующая итерация может разделить 3 на 1,2.

Немного более очевидный факт заключается в том, что если вы пытались 3,5, тогда вам не нужно пытаться 5,3.

Так что если вы вводите 8, то вы пытаетесь 8, 1,7, 2,6, 3,5, 4,4 и сравните результаты, выбрав самый большой.Из предоставленной вами заглушки метода я предполагаю, что вам не нужно возвращать то, как вы достигли этого результата, только сам максимальный результат