背包问题(经典) [英] knapsack problem (classic)

问题描述

因此，我必须在上课时解决背包问题.到目前为止，我已经提出了以下建议.我的比较器是确定两个主题中哪个主题更好的函数(通过查看相应的(值，工作)元组).

So I have to solve the knapsack problem for class. So far, I've come up with the following. My comparators are functions that determine which of two subjects will be the better option (by looking at the corresponding (value,work) tuples).

我决定对工作量小于maxWork的可能主题进行迭代，为了找出在任何给定回合中哪个主题是最佳选择，我将最近的主题与我们尚未使用的所有其他主题进行了比较

I decided to iterate over the possible subjects with work less than maxWork, and in order to find which subject is the best option at any given turn, I compared my most recent subject to all the other subjects that we have not used yet.

def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """

    optimal = {}
    while maxWork > 0:
        new_subjects = dict((k,v) for k,v in subjects.items() if v[1] < maxWork)
        key_list = new_subjects.keys()
        for name in new_subjects:
            #create a truncated dictionary
            new_subjects = dict((name, new_subjects.get(name)) for name in key_list)
            key_list.remove(name)
            #compare over the entire dictionary
            if reduce(comparator,new_subjects.values())==True:
                #insert this name into the optimal dictionary
                optimal[name] = new_subjects[name]
                #update maxWork
                maxWork = maxWork - subjects[name][1]
                #and restart the while loop with maxWork updated
                break
    return optimal  

问题是我不知道为什么这是错误的.我遇到了错误，而且我不知道我的代码在哪里出错(即使在抛出print语句之后).非常感谢您的帮助，谢谢！

The problem is I don't know why this is wrong. I'm getting errors and I have no idea where my code is wrong (even after throwing in print statements). Help would be much appreciated, thanks!

推荐答案

与OPT相比，使用简单的贪心算法不会对解决方案的质量产生任何限制.

Using a simple greedy algorithm will not provide any bounds on the quality of the solution in comparison to OPT.

这里是一个完全多项式时间(1-epsilon)*背包的OPT近似伪代码:

Here is a fully polynomial time (1 - epsilon) * OPT approximation psuedocode for knapsack:

items = [...]  # items
profit = {...} # this needs to be the profit for each item
sizes = {...}  # this needs to be the sizes of each item
epsilon = 0.1  # you can adjust this to be arbitrarily small
P = max(items) # maximum profit of the list of items
K = (epsilon * P) / float(len(items))
for item in items:
    profit[item] = math.floor(profit[item] / K)
return _most_prof_set(items, sizes, profit, P)

我们现在需要定义最有利可图的设置算法.我们可以通过一些动态编程来做到这一点.但是首先让我们回顾一些定义.

We need to define the most profitable set algorithm now. We can do this with some dynamic programming. But first lets go over some definitions.

如果P是集合中利润最高的项目，而n是我们拥有的项目数量，则nP显然是允许的利润的微不足道的上限.对于{1，...，n}中的每个i和{1，...，nP}中的p，我们让Sip表示总利润为精确 p且总大小的项的子集被最小化.然后，让A(i，p)表示集合Sip的大小(如果不存在，则为无穷大).我们可以很容易地证明，{1，...，nP}中p的所有值都已知A(1，p).我们将定义一个递归来计算A(i，p)，并将其用作动态规划问题，以返回近似解.

If P is the most profitable item in the set, and n is the amount of items we have, then nP is clearly a trivial upper bound on the profit allowed. For each i in {1,...,n} and p in {1,...,nP} we let Sip denote a subset of items whose total profit is exactly p and whose total size is minimized. We then let A(i,p) denote the size of set Sip (infinity if it doesn't exist). We can easily show that A(1,p) is known for all values of p in {1,...,nP}. We will define a recurrance to compute A(i,p) which we will use as a dynamic programming problem, to return the approximate solution.

A(i + 1, p) = min {A(i,p), size(item at i + 1 position) + A(i, p - profit(item at i + 1 position))} if profit(item at i + 1) < p otherwise A(i,p)

最后我们给_most_prof_set

Finally we give _most_prof_set

def _most_prof_set(items, sizes, profit, P):
    A = {...}
    for i in range(len(items) - 1):
        item = items[i+1]
        oitem = items[i]
        for p in [P * k for k in range(1,i+1)]:
            if profit[item] < p:
                A[(item,p)] = min([A[(oitem,p)], \
                                     sizes[item] + A[(item, p - profit[item])]])
            else:
                A[(item,p)] = A[(oitem,p)] if (oitem,p) in A else sys.maxint
    return max(A) 

来源

这篇关于背包问题(经典)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！