Это интересная проблема, хотя на самом деле это не вопрос StackOverflow, но я не смог устоять:).
Ниже приведено решение, которое дает мое собственное решение, и простое решение методом грубой силы (для проверки результаты), а также время, необходимое для 10 000 выполнений каждого и вашего решения:
from random import randint
from collections import namedtuple
from itertools import combinations
from timeit import timeit
Article = namedtuple('Article', ['id', 'pages', 'value'])
def get_articles(min_pages, max_pages, min_value, max_value, number_of_articles):
return [Article(n, randint(min_pages, max_pages), randint(min_value, max_value)) for n in range(number_of_articles)]
def _sort_articles_by_relative_value(articles):
return list(reversed(sorted(articles, key=lambda a: a.value / a.pages)))
def _pick_articles_recursive(articles, pages_read_limit, n=0, picked=None, pages=0, value=0):
if picked is None:
picked = []
while n < len(articles):
if pages + articles[n].pages == pages_read_limit:
return pages_read_limit, value + articles[n].value, picked + [articles[n]]
elif pages + articles[n].pages < pages_read_limit:
inclusive = _pick_articles_recursive(
articles, pages_read_limit, n+1,
picked + [articles[n]], pages + articles[n].pages, value + articles[n].value)
if inclusive[0] == pages_read_limit:
return inclusive
else:
exclusive = _pick_articles_recursive(
articles, pages_read_limit, n+1,
picked, pages, value)
if inclusive[1] > exclusive[1]:
return inclusive
else:
return exclusive
n += 1
return pages, value, picked
def pick_articles(articles, pages_read_limit):
articles = _sort_articles_by_relative_value(articles)
return _pick_articles_recursive(articles, pages_read_limit)
def pick_articles_brute(articles, pages_read_limit):
bv = 0
bp = []
for n in range(len(articles)+1):
for picked_articles in combinations(articles, n):
nv = sum([a.value for a in picked_articles])
np = sum([a.pages for a in picked_articles])
if nv > bv and np <= pages_read_limit:
bp = picked_articles
bv = nv
return sum([a.pages for a in bp]), bv, bp
def max_iv(pages, ivs, pages_read_limit):
max_iv = 0
for lgth in range(1,len(pages)+1):
reading_options = combinations(range(len(pages)),lgth)
for ro in reading_options:
if sum((pages[x] for x in ro)) <= pages_read_limit:
iv = sum((ivs[x] for x in ro))
if iv > max_iv:
max_iv = iv
def main():
articles = get_articles(min_pages=1, max_pages=5, min_value=1, max_value=5, number_of_articles=6)
result_new = pick_articles(articles, pages_read_limit=10)
result_brute = pick_articles_brute(articles, pages_read_limit=10)
print('articles :', articles)
print('result :', result_new)
print('brute :', result_brute)
print('t result :', timeit(lambda: pick_articles(articles, pages_read_limit=10), number=10000))
print('t brute :', timeit(lambda: pick_articles_brute(articles, pages_read_limit=10), number=10000))
print('t max_iv :', timeit(lambda: max_iv(
pages=[a.pages for a in articles], ivs=[a.value for a in articles], pages_read_limit=10), number=10000))
main()
Типичный результат:
articles : [Article(id=0, pages=1, value=5), Article(id=1, pages=2, value=2), Article(id=2, pages=3, value=4), Article(id=3, pages=4, value=3), Article(id=4, pages=5, value=3), Article(id=5, pages=2, value=4)]
result : (10, 16, [Article(id=0, pages=1, value=5), Article(id=5, pages=2, value=4), Article(id=2, pages=3, value=4), Article(id=3, pages=4, value=3)])
brute : (10, 16, (Article(id=0, pages=1, value=5), Article(id=2, pages=3, value=4), Article(id=3, pages=4, value=3), Article(id=5, pages=2, value=4)))
t result : 0.0626382
t brute : 0.6400916000000001
t max_iv : 0.5818494999999999
Обратите внимание, что он не всегда выполняет это хорошо, но всегда лучше, чем два других. Приведенные результаты довольно типичны. Также обратите внимание, что результат не обязательно совпадает с решением грубой силы, но значение будет. В некоторых случаях разные подходы находят разное количество статей, в еще более редких случаях даже разное количество страниц, но они всегда будут находить оптимальную оценку.
Наконец, обратите внимание, что _sort_articles_by_relative_value и _pick_articles_recursive вместе мы дадим вам ответ, остальная часть кода предназначена для сравнения и создания привлекательного вида.
Решение работает, потому что оно начинается с вычисления среднего значения на страницу для каждой статьи и сортировки статей. от наибольшего значения на страницу до самого низкого значения на страницу. Имея это в виду, имеет смысл, что если вы выбираете статьи слева направо, как только вы достигнете максимального количества страниц, нет смысла пробовать другие комбинации со статьями справа, так как среднее значение на страницу любая комбинация всегда будет ниже, и общее количество страниц не может превышать максимальное.