时间戳

首页 > 解决方案 > 蟒蛇回溯背包

python - 蟒蛇回溯背包

问题描述

这是我到目前为止的代码：

   def frac_knapsack(n,size, profit,K):
    if K <= 0:
       return 0
    for i in range(0,i):
        if profit[i]/size[i]>profit[i-1]/size[i-1]:
            profit.append[i] and size.append[i]
    s = 0
    p = 0
    for i in range(n):
        if s + size[i] <= K:
            p += profit[i]
            s += size[i]
        else: 
            p += (K-s) * (profit[i]/size[i])
            s = K
            break
        return p
def Knapsack(i, size):
    if i > n or size <= 0:
        print(x)
        return
    if x[j] == 1:
        for j in range(0,i-1):
           p+=P[j]
    if x[j] == 1:
        for j in range(0,i-1):
           s+=S[j]
    if x[i] == 1:
        if s+size[i] <= K and (p + profit[i] + B) > MaxProfit:
            B = fractional_Knapsack(n-(i+1), size[i+1:], profit[i+1:], T-size[i])
        if p+profit[i] > MaxProfit:
            MaxProfit=p+profit[i]
            x=solution
        Knapsack(i+1, T-size[i])
        if x[i] == 0:
            B = frac_Knapsack(n-(i+1), size[i+1:], profit[i+1:], T)
        if (p + B) > MaxProfit:
            Knapsack(i+1, T)
  1. 我在第 4 行排序时遇到问题。我必须将其排序为重量效率。我需要使用快速排序算法吗？
  2. 我想输入四件事：n、大小、利润和 K 我需要使用地图吗？规模和利润是清单吗？

标签： pythonbacktrackingknapsack-problem

解决方案

你用过

B = fractional_Knapsack(n-(i+1), size[i+1:], profit[i+1:], T)

你的方法被称为

def frac_knapsack(n,size, profit,K):

推荐阅读