Knapsack背包问题：n个物品有重量W={w 1,…,wn}和价值P={p 1,…,pn}, 有一容量为C的背包（其中wi ,p I, CZ+）。如何选择物品装入背包，是装入物品的价值最大？ 要求： 1）编写算法，按单位重量的价值由大到小排序，重新编号。 2）编写算法int InitProfit()求出初始解bestp； 3）编写算法float Bound(int i)求出上界值； 4）编写回溯算法void Backtrack(int t)求出最优解和最优值。 5）实例：n=11, wi随机产生，范围1~20；p i随机产生，范围10~30；C等于所有物品重量和的4/5（取整数）。编写程序，将结果打印到文件（Knapsack.txt）。

好的，下面是完整的代码实现：

import random

# 物品的重量和价值
weights = []
values = []
# 物品数量
n = 11
# 背包容量
C = 0
# 按单位重量价值由大到小排序后的物品编号
sorted_items = []
# 当前最优解和最优值
bestp = []
maxp = 0

# 计算每个物品的单位重量价值并排序
def sort_items():
    global sorted_items
    unit_values = [(i, values[i] / weights[i]) for i in range(n)]
    sorted_items = [i[0] for i in sorted(unit_values, key=lambda x: x[1], reverse=True)]

# 计算初始解
def init_profit():
    global bestp
    bestp = [0] * n
    return 0

# 计算上界值
def bound(i):
    global C, weights, values, bestp
    # 剩余容量
    space = C
    # 当前背包的总价值
    total_value = 0
    # 将单位重量价值最高的物品装满
    j = i
    while j < n and space >= weights[sorted_items[j]]:
        space -= weights[sorted_items[j]]
        total_value += values[sorted_items[j]]
        j += 1
    # 能够装满
    if j < n:
        total_value += space * values[sorted_items[j]] / weights[sorted_items[j]]
    return total_value

# 回溯搜索
def backtrack(t):
    global maxp, bestp, C, weights, values
    if t == n:
        # 已经搜索完所有物品，更新最优解和最优值
        if maxp < sum([bestp[i] * values[i] for i in range(n)]):
            maxp = sum([bestp[i] * values[i] for i in range(n)])
            with open('Knapsack.txt', 'w') as f:
                f.write(f"最优解：{bestp}\n最优值：{maxp}")
    else:
        # 不装入当前物品
        if bound(t) > maxp:
            backtrack(t+1)
        # 装入当前物品
        if weights[sorted_items[t]] <= C:
            C -= weights[sorted_items[t]]
            bestp[sorted_items[t]] = 1
            if bound(t+1) > maxp:
                backtrack(t+1)
            C += weights[sorted_items[t]]
            bestp[sorted_items[t]] = 0

# 生成随机数据并计算背包容量
def generate_data():
    global weights, values, C
    weights = [random.randint(1, 20) for i in range(n)]
    values = [random.randint(10, 30) for i in range(n)]
    C = sum(weights) * 4 // 5

# 测试
if __name__ == '__main__':
    generate_data()
    sort_items()
    init_profit()
    backtrack(0)

运行该程序后，将在当前目录下生成一个名为 `Knapsack.txt` 的文件，其中包含最优解和最优值。