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

Question

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

Дали монету п (<= 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/

3

algorithm c++dynamic-programming space-complexity time-complexity

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Во-первых, твой подход вполне разумен. У вас есть номера до 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] и запомни все номера i где count[i]>=L, Однако, как уже упоминалось, эта процедура является слишком дорогостоящей, так как она должна быть сделана во время самого запуска.

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

0