时间戳

首页 > 解决方案 > Python编程问题——确定阅读文章的正确组合以实现最大的智力价值

python - Python编程问题——确定阅读文章的正确组合以实现最大的智力价值

问题描述

最近遇到一个这样的编程问题。

一套可以看的白皮书，比如说4。页数分别是4、4、6、8。每篇文章的知识价值分别是2、4、4、5。一个人最多只能阅读 15 页。您会选择阅读哪些文章，以最大限度地提高获得的知识价值？

我想出的Python解决方案如下。如果我将 article_count 增加到 20，则程序需要更长的时间才能完成。你能帮忙提出优化它的方法吗？1. 内存效率更高 2. 消除组合，从而减少迭代 3. 算法/数据结构改进

from memory_profiler import profile
from itertools import combinations
import numpy as np

@profile
def max_iv(articles_count, 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
    print(max_iv)

if __name__ == '__main__':
    articles_count = 4
    pages = np.random.randint(1,10,articles_count)
    ivs=np.random.randint(1,10,articles_count)
    pages_read_limit = 15
    max_iv(articles_count, pages, ivs, pages_read_limit)

标签： pythonoptimizationmemorycombinations

解决方案

这是一个有趣的问题，虽然不是真正的 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一起给您答案，其余代码只是为了进行比较并使事情看起来不错。

该解决方案之所以有效，是因为它首先计算每篇文章的每页平均值，然后将文章从每页的最大值到每页的最小值进行排序。考虑到这一点，如果你从左到右选择文章，一旦达到最大页数，就没有必要尝试与右边文章的其他组合，因为每页的平均值任何组合都将始终较低，并且总页数不能超过最大值。

推荐阅读