Вирішую завдання про розмін монет. Умова наведено нижче. Проблема в тому, що всі рішення, які я випробував займають багато пам'яті. І не застосовні для великих вхідних даних наприклад, для 1 000 000 000. Питання в тому як можна оптимізувати рішення для великих чисел? Або може є якась більш ефективна ідея для вирішення цього завдання?
За даними числах 1≤n≤30 і 1≤w≤10 ^ 9 і набору чисел 1≤v [1], ..., v [n] ≤10 ^ 9 знайдіть мінімальне число k. для якого число w можна уявити як суму k чисел з набору. Кожне число з набору можна використовувати скільки завгодно раз. Відомо, що в наборі є одиниця і що для будь-якої пари чисел з набору одне з них ділиться на інше. Гарантується, що в оптимальному відповіді число доданків не перевищує 10 ^ 4.
Виведіть число k і самі складові.
Проміжні масиви не потрібні:
Через те, що ми target завжди ділимо на найбільшу з можливих, result завжди нарощується на найменшу з можливих чисел. В кінці у нас 1 по умові.
У список обраних монет включаємо ті, які менше цільової суми target - раз монета менше значить їй можна розміняти.
Чому алгоритм видає найкраще рішення? Тому, що в умові сказано:
для будь-якої пари чисел з набору одне з них ділиться на інше
Це означає, що будь-яке число з набору ділиться на будь-яке число з набору менше першого. По суті, число перед 1 повинно бути НСД всіх чисел. Тому ми маємо право їх впорядкувати і діяти як я пропоную. Якби вони не мали НСД, то тоді так, потрібно було б перебирати варіанти розміну.
відповідь дан 7 дек '15 в 9:57