В моем приложении мне нужно определить, какие плиты пользователь может загрузить на штангу, чтобы достичь желаемого веса.object-c ищет алгоритм
Например, пользователь может указать, что у них есть 45LB bar, и использовать 45,35,25,10,5,2.5 фунта. Для веса, подобного 115, это непростая задача, так как результат аккуратно соответствует общей пластине. 115 - 45/2 = 35.
Таким образом, целью здесь является поиск самой большой и наименьшей пластины (ов) (от выбора), которую пользователь должен достичь веса.
Мой метод стартер выглядит следующим образом ...
-(void)imperialNonOlympic:(float)barbellWeight workingWeight:(float)workingWeight {
float realWeight = (workingWeight - barbellWeight);
float perSide = realWeight/2;
.... // lots of inefficient mod and division ....
}
Мой мыслительный процесс является первым определить, что вес каждой стороны будет. Общий вес - вес штанги/2. Затем определите, какой должна быть наибольшая из наименьших требуемых пластин (и количество каждого из них, например 325, было бы 45 * 3 + 5 или 45,45,45,5.
Прошив fmodf и пару других идей, мне пришло в голову, что может быть алгоритм, который решает эту проблему. Я изучал BFS и признал, что он выше моей головы, но все же готов дать ему шанс.
Цените любые советы о том, где искать в алгоритмах или примеры кода.
Вам не нужен алгоритм, как вы его уже знаете. Это легко сделать, просто пойдите с наибольшим весом, пока остальные меньше этого, и продолжайте спускаться и заканчивайте 5-точечными весами. –
@JamesBlack это не сработает. Проблема мин-монеты (решена с использованием DP). вы не можете следовать процедуре, которую вы сказали, например, допустим, что общий вес = 123, а весы - 50,41,1. В соответствии с вашим решением у вас будет 123 = 50 * 2 + 23 * 1 (всего 25 элементов), но 123 = 41 * 3, 3 - лучшее решение. Для его использования вам необходимо использовать динамическое программирование. http://stackoverflow.com/questions/4247662/the-minimum-number-of-coins-the-sum-of-which-is-s – santhu
Thanek, santhu. Это хорошо описывает проблему, и ваша ссылка дает мне возможность начать ее решать. – Jeremy