Python回溯法背包问题：重量效率排序与输入处理咨询

First, let's take a look at your current code (fixed HTML escape characters like < to actual operators for clarity):

def frac_knapsack(n, size, profit, K):
    if K <= 0:
        return 0
    # Your current sorting logic has issues here
    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)

Q1: Do I need to use QuickSort for sorting by profit/size ratio? #

Short answer: No, you don't need to implement QuickSort yourself. Python's built-in sorting functions are way more efficient and reliable here—they use Timsort, a hybrid algorithm that outperforms standard QuickSort for most real-world datasets and handles edge cases better.

Your current sorting code has syntax and logic errors (like range(0,i) where i is undefined, and incorrect append usage). Instead, you should pair each item's size and profit together, sort the pairs by their unit value (profit/size) in descending order, then split them back into separate lists. Here's how to fix that part:

# Pair size and profit, sort by unit value descending
items = sorted(zip(size, profit), key=lambda x: x[1]/x[0], reverse=True)
# Split back into size and profit lists
sorted_size = [item[0] for item in items]
sorted_profit = [item[1] for item in items]

Replace your broken sorting loop with this code inside frac_knapsack, and use sorted_size and sorted_profit for the rest of the calculation.

Q2: Do I need to use map to input list-type size and profit? #

Absolutely! Using map is the cleanest, most common way to convert user input strings into numeric lists in Python. Here's a step-by-step example of how to handle input properly:

# Get input for n (number of items)
n = int(input("Enter number of items: "))

# Get size list: input n space-separated integers
print(f"Enter {n} item sizes separated by spaces:")
size = list(map(int, input().split()))
# Optional: validate input length to avoid errors
while len(size) != n:
    print(f"Oops, please enter exactly {n} sizes!")
    size = list(map(int, input().split()))

# Get profit list: same logic as size
print(f"Enter {n} item profits separated by spaces:")
profit = list(map(int, input().split()))
while len(profit) != n:
    print(f"Oops, please enter exactly {n} profits!")
    profit = list(map(int, input().split()))

# Get knapsack capacity K
K = int(input("Enter knapsack capacity: "))

This code takes user input, converts space-separated strings into integer lists using map(int, ...), and adds basic validation to ensure the input matches the expected number of items.

A quick heads-up on your 0-1 knapsack function (Knapsack): It has several undefined variables (like n, K, x, MaxProfit) and inconsistent function names (e.g., fractional_Knapsack vs frac_knapsack). You'll want to pass these as parameters or define them properly to avoid runtime errors.

内容的提问来源于stack exchange，提问作者DIfficulttolearn