回溯算法计算学生购买的书籍

trackback.py

import random
import copy

# student_fees 每个学生交的钱
# 每本书的价格
def solve(student_fees, book_nums, book_price):
    track = [[] for x in range(len(student_fees))]
    result = []

    def backtrack(i):
        if i == len(student_fees):
            nonlocal result
            result.append(copy.deepcopy(track))
            return

        curr = sum(book_price[x] for x in track[i])
        if curr == student_fees[i]:
            backtrack(i + 1)
        if curr < student_fees[i]:

            for bi in range(len(book_nums)):

                # 学生持有的书的总价小于已知数
                if book_nums[bi] > 0 and bi not in track[i]:
                    # 未持有这本书
                    book_nums[bi] -= 1
                    track[i].append(bi)
                    backtrack(i)
                    track[i].pop()
                    book_nums[bi] += 1

    backtrack(0)
    return result


if __name__ == '__main__':
    n_student = 10
    max_book_per_student = 3
    uniq_books = 8  # 一共有8种书
    d = set()
    book_price = []
    while len(book_price) != uniq_books:
        price = random.randint(5, 30)
        if price not in d:
            d.add(price)
            book_price.append(price)

    book_nums = [0 for x in range(uniq_books)]
    student_fees = [0 for x in range(n_student)]
    res = [[] for x in range(n_student)]
    for i in range(n_student):
        # 每个学生随机选1-3本书
        for j in range(random.randint(1, max_book_per_student)):

            book = random.randint(0, uniq_books - 1)
            if book not in res[i]:
                student_fees[i] += book_price[book]
                book_nums[book] += 1
                res[i].append(book)
    print("书籍的价格:{}".format(book_price))
    print("书籍的数量:{}".format(book_nums))
    print("学生的交费:{}".format(student_fees))
    print("学生买的书:{}".format(res))
    result = solve(student_fees, book_nums, book_price)
    print(len(result))
    print(result)
    for r in result:

        print("结算的结果:{}".format(r))
        book_nums2 = [0 for x in range(uniq_books)]
        student_fees2 = [0 for x in range(n_student)]
        for i, stu in enumerate(r):
            for bi in stu:
                book_nums2[bi] += 1
                student_fees2[i] += book_price[bi]
        print("还原的书籍数量:{}".format(book_nums2))
        print("还原的学生费用:{}".format(student_fees2))