Наибольшее количество при использовании динамического программирования

Question

Учитывая монету n (< = 10^9), я могу обменять ее на 3 монеты: n/2, n/3 и n/4 (где / представляет разделение полов). Какую максимальную сумму я могу сделать? Мой код:

#include <iostream> 
using namespace std; 
int a[10000000]; 
long int coin(long int n){ 
    if(n<10000000){ 
     return a[n]; 
    } 
    else{ 
     return(max(n,coin(n/2)+coin(n/3)+coin(n/4))); 
    } 
} 
int main() 
{ 
    //cout << "Hello World!" << endl; 
    long int n,ans; 
    int i; 
    a[0]=0; 
    for(i=1;i<10000000;i++){ 
     a[i]=max(i,a[i/2]+a[i/3]+a[i/4]); 
    } 
    while(cin>>n){ 
     if(n<10000000){ 
      cout<<a[n]<<endl; 
     } 
     else{ 
      ans=coin(n); 
      cout<<ans<<endl; 
     } 
    } 
    return 0; 
} 

Как я могу улучшить свое время и пространство? Задача: https://www.hackerearth.com/problem/algorithm/bytelandian-gold-coins/description/

Answer 1

Несколько мыслей, никакого определенного ответа пока нет.

• Во-первых, ваш подход вполне разумный. У вас есть номера до 10^9, которые вы не можете предварительно обработать. Вместо этого вы принимаете во внимание, что меньшие числа «как-то» чаще всего выбираются процессом, и поэтому вы мнимаете только до некоторой верхней границы, здесь 10^7.

• Легкое улучшение в вашем базовом алгоритме заключается в том, что вам необходимо помнить только цифры 2 или 3. Все остальные входы могут быть легко связаны с этими числами в функции count.

• Другая оптимизация может заключаться в том, чтобы эмпирически изменить верхнюю границу 10^7. То есть, выберите некоторые значения между, скажем, 10^5 и 10^8, а затем введите один с минимальным временем выполнения.

---

Улучшение этого основного подхода не является тривиальной, но способ улучшить его путем получать представление о процедуре выбора номера. В принципе, следует помнить те числа, которые выбраны чаще, и оставлять эти цифры, которые выбраны всего несколько раз.

Здесь можно многое сделать, но обычно требуемые результаты, на которых основана процедура напоминания, должны быть созданы «на лету» в программе, которую вы подаете на конкурс. Думаю, это затрудняет разработку конкурентных решений. Я мог представить себе, что простые правила формы "memoize all below 10.000", "memoize multiples of 5 above 10.000", "memoize multiples of 7 above 10.000" и т. Д. Могут быть полезны. Такие правила могут быть легко закодированы в программу, не требуя слишком большого объема памяти. Например, они могут быть найдены заранее генетическими алгоритмами.

---

Для точного подхода можно принять равномерное распределение номеров монет в задаче. Затем можно перебрать все числа i до 10^9 и получить информацию о том, как часто каждый номер k<i выбирается процедурой. Результатом является массив count[i]. Затем выберете нижнюю границу L за count[i] и memoize все номера i где count[i]>=L. Однако, как уже упоминалось, эта процедура слишком дорогостоящая, как это должно быть сделано в самом запуске.

Вместо этого вы можете выбрать только, скажем, N наиболее часто встречающиеся номера и жестко закодировать их в коде. Фактическое число N включенных номеров memoizaion может быть определено ограничением памяти в задаче.