Скрипт перебора и суммы

@lemuriec · Регистрация: 30.03.2010

Студворк — интернет-сервис помощи студентам

Добрый день. Очень нужна помощь. Подскажите возможно ли на питоне решить следующую задачу. Есть определенные 6 чисел: 256, 304, 397, 465 , 477, 497 . Нужно сколько угодно их складывая получить число 4600 (не обязательно использовать все числа). Это возможно? Например используя число 256 - 13 раз, 397 - 2 раза, 477 - 1 раз получаю 4599. Понимаю что нужно циклом перебирать, но как обозначить условия не могу в голове сообразить.

Заранее благодарю

@EpicNoob · 25.12.2018, 17:20

Можно так

Python
1
2
3
4
5
6
7
8
9
from random import random
arr = [256,304,397,465,477,497]
N = 0
while N != 4600:
    m = int(random()*5)
    N = N + arr[m]
    if N > 4600:
        N = 0
    print(arr[m],N)

Где в переменной N суммируются элементы списка arr,состоящий из ваших значений.
Если из рандомных значений превышает 4600,счётчик обнуляется.

Рыжий Лис · 25.12.2018, 17:37

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np
 
ls = np.array((256, 304, 397, 465, 477, 497))
val = 4600
 
def main():
    k = np.zeros_like(ls)
    
    def check(i=0):
        v = sum(ls * k)
        if v == val:
            raise ValueError(k)
        elif v > val:
            k[i] = 0
            k[i + 1] += 1
            check(i + 1)        
    
    while True:
        k[0] += 1
        print(k)
        check()
 
main()

ответ: [2 3 8 0 0 0]

Добавлено через 48 секунд
>>> 2*256 + 3*304 + 8*397
4600

Добавлено через 8 минут
Все комбинации:
[2 3 8 0 0 0]
[2 8 3 1 0 0]
[10 1 2 1 1 0]
[3 1 3 4 1 0]
[7 3 0 1 3 0]
[0 3 1 4 3 0]
[4 0 3 0 5 0]
[1 2 1 0 7 0]
[9 2 3 0 0 1]
[2 2 4 3 0 1]
[6 4 1 0 2 1]
[2 1 0 6 0 2]
[3 0 0 2 4 2]
[2 1 1 1 3 3]
[4 0 4 0 0 4]
[1 2 2 0 2 4]

@lemuriec · 25.12.2018, 17:58 **[ТС]**

Чувак. ты бог! Спасибо!

Добавлено через 14 минут
Рыжий Лис, Извиняюсь за нескромную просьбу.... если не трудно... можешь пояснить решение? Мне приятно, что ты сразу выдал код, но хотелось бы для себя понять, что он делает.

Заранее благодарю

Рыжий Лис · 25.12.2018, 18:30

Ну, берём два вектора (списка), один ls - с цифрами, другой k - коэффициенты, то есть то количество раз, сколько нужно взять само число. Векторы взяты для удобства умножения, чтобы не писать цикл.

И дальше сам перебор:
Начальный вектор
[0 0 0 0 0 0]
Добавляем единичку
[1 0 0 0 0 0]
Считаем сумму и сравниваем:
1*256 + 0*… + 0*… + … = 256
Что ж, сумма не совпала, добавляем ещё единичку:
[2 0 0 0 0 0]
2*256 + 0*… + 0*… + … = 512
итд.

Но самое интересное происходит при v > val. Дальше перебор делать не имеет смысла, ведь сумма уже больше числа 4600 и будет только расти. Что мы делаем? Обнуляем первый разряд и добавляем единичку дальше. Уходим в рекурсию (сдвигаемся на разряд вправо).

Вот этот момент:
[17 0 0 0 0 0]
[18 0 0 0 0 0] # 18*256 > 4600
[0 1 0 0 0 0]
[1 1 0 0 0 0]
[2 1 0 0 0 0]

Добавлено через 1 минуту
Если решение нашли, то бросаем исключение (так проще, ведь мы можем находиться на неизвестной глубине рекурсии).

@lemuriec · 25.12.2018, 19:53 **[ТС]**

Рыжий Лис, А как сделать, чтобы он продолжил искать возможные варианты решения, а не останавливался на первом найденном?

Рыжий Лис · 26.12.2018, 04:53

Ловить исключение и продолжать цикл.

@lemuriec · 26.12.2018, 11:10 **[ТС]**

Рыжий Лис, Спасибо большое. Разобрался в коде) Питон мощщщ ))

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@lemuriec 11 / 11 / 2 Регистрация: 30.03.2010 Сообщений: 199

	Скрипт перебора и суммы 25.12.2018, 16:37. Показов 6590. Ответов 7 Метки нет (Все метки) Добрый день. Очень нужна помощь. Подскажите возможно ли на питоне решить следующую задачу. Есть определенные 6 чисел: 256, 304, 397, 465 , 477, 497 . Нужно сколько угодно их складывая получить число 4600 (не обязательно использовать все числа). Это возможно? Например используя число 256 - 13 раз, 397 - 2 раза, 477 - 1 раз получаю 4599. Понимаю что нужно циклом перебирать, но как обозначить условия не могу в голове сообразить. Заранее благодарю 0

@lemuriec 11 / 11 / 2 Регистрация: 30.03.2010 Сообщений: 199
	25.12.2018, 17:58 [ТС]
	Чувак. ты бог! Спасибо! Добавлено через 14 минут Рыжий Лис, Извиняюсь за нескромную просьбу.... если не трудно... можешь пояснить решение? Мне приятно, что ты сразу выдал код, но хотелось бы для себя понять, что он делает. Заранее благодарю 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	25.12.2018, 18:30
	Ну, берём два вектора (списка), один `ls` - с цифрами, другой `k` - коэффициенты, то есть то количество раз, сколько нужно взять само число. Векторы взяты для удобства умножения, чтобы не писать цикл. И дальше сам перебор: Начальный вектор [0 0 0 0 0 0] Добавляем единичку [1 0 0 0 0 0] Считаем сумму и сравниваем: 1256 + 0… + 0… + … = 256 Что ж, сумма не совпала, добавляем ещё единичку: [2 0 0 0 0 0] 2256 + 0… + 0… + … = 512 итд. Но самое интересное происходит при `v > val`. Дальше перебор делать не имеет смысла, ведь сумма уже больше числа 4600 и будет только расти. Что мы делаем? Обнуляем первый разряд и добавляем единичку дальше. Уходим в рекурсию (сдвигаемся на разряд вправо). Вот этот момент: [17 0 0 0 0 0] [18 0 0 0 0 0] # 18256 > 4600 [0 1 0 0 0 0] [1 1 0 0 0 0] [2 1 0 0 0 0] Добавлено через 1 минуту* Если решение нашли, то бросаем исключение (так проще, ведь мы можем находиться на неизвестной глубине рекурсии). 1

@lemuriec 11 / 11 / 2 Регистрация: 30.03.2010 Сообщений: 199
	25.12.2018, 19:53 [ТС]
	Рыжий Лис, А как сделать, чтобы он продолжил искать возможные варианты решения, а не останавливался на первом найденном? 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	26.12.2018, 04:53
	Ловить исключение и продолжать цикл. 1

@lemuriec 11 / 11 / 2 Регистрация: 30.03.2010 Сообщений: 199
	26.12.2018, 11:10 [ТС]
	Рыжий Лис, Спасибо большое. Разобрался в коде) Питон мощщщ )) 0

Опции темы

Скрипт перебора и суммы

Решение