Алгоритмическая головоломка

Question

Как распределить 1000 $ в десяти ящиках, чтобы можно было указать любую сумму в размере от 1 до 1000 долларов США (оба включительно) в виде некоторых комбинаций этих полей.

Просьба указать любые подсказки о том, как подойти к этому. Я попытался, но не смог решить какое-либо решение.

Answer 1

Напиши все числа от 1 до 1000 в представлении base-two. Эти цифры требуют десяти бит с 2^10 = 1024. Ваши боксы имеют две до 2^8 и 489 для последней коробки (2^0 - 2^8 и 489 - десять коробок и 2^0 + 2^1 + ... + 2^8 + 489 = 2^9 - 1 + 489 = 511 + 489 = 1000), а представления бит дают вам доказательства того, что вы можете написать любое число до 1000 в качестве комбинации эти ящики (очевидно, что-то до 511 в порядке, для чего-то большего, чем 511, вычесть 489, а затем обратите внимание, что вы можете записать остаток в виде комбинации из остальных 8 ящиков, так как гарантировано будет меньше или равно 511).

Answer 2

Вы когда-нибудь делали двоичное преобразование в десятичное целое? Возьмите любое число от 1 до 1000 и попробуйте преобразовать его в двоичный. Вы выяснить, что вы имеете дело по степеням 2.

Распределить по степеням 2, а затем на любую сумму, вам нужно, просто превратить его в двоичную и выбрать те окна, для которых установлен бит 1.