速求，对多种商品的购买力优化问题（用遗传算法、枚举法、粒子群算法、模拟退火算法等方法求解）

Question

一、问题描述
假设有有8个商店，商店 A 、商店 B、商店 C 、商店 D、商店 E 、商店 F、商店 G 和商店 H。每个商店卖不同种类的商品，
商品价格如下：
商店 A ：牛奶500元；商店 B：香蕉800元；商店 C：梨1200元 ；商店 D：饺子800元；商店 E：西瓜1500元 ；商店 F：菠萝100元；商店 G：枣90元；商店 H：葡萄200元。
共有10个顾客进行采购，每个商品的顾客需求量为：牛奶=[4, 0, 0, 0, 4, 0, 0, 0, 0, 0],
香蕉=[4, 5, 5, 5, 4, 5, 5, 4, 5, 5],
梨= [3, 4, 4, 4, 3, 4, 4, 3, 4, 4],
饺子= [5, 0, 0, 0, 5, 0, 0, 5, 0, 0],
西瓜= [0, 3, 3, 3, 0, 3, 3, 0, 3, 3],
菠萝=[13, 24, 24, 24, 0, 0, 0, 0, 0, 0],
枣= [26, 49, 49, 49, 26, 49, 49, 0, 0, 0],
葡萄= [5, 7, 7, 7, 5, 7, 7, 0, 0, 0]]。各种商品的存货量为牛奶25个
香蕉55个
梨25个
饺子30个
西瓜30个
菠萝80个
枣120个，葡萄20个。求每个顾客必须根据自身顾客需求量买到至少一样商品，并且总花费最少。输出商品花费、每个顾客购买的商品及数量

Answer 1

# 商品价格和库存
prices = {
    '牛奶': 500,
    '香蕉': 800,
    '梨': 1200,
    '饺子': 800,
    '西瓜': 1500,
    '菠萝': 100,
    '枣': 90,
    '葡萄': 200
}

stocks = {
    '牛奶': 25,
    '香蕉': 55,
    '梨': 25,
    '饺子': 30,
    '西瓜': 30,
    '菠萝': 80,
    '枣': 120,
    '葡萄': 20
}

# 顾客需求量
demands = {
    '牛奶': [4, 0, 0, 0, 4, 0, 0, 0, 0, 0],
    '香蕉': [4, 5, 5, 5, 4, 5, 5, 4, 5, 5],
    '梨': [3, 4, 4, 4, 3, 4, 4, 3, 4, 4],
    '饺子': [5, 0, 0, 0, 5, 0, 0, 5, 0, 0],
    '西瓜': [0, 3, 3, 3, 0, 3, 3, 0, 3, 3],
    '菠萝': [13, 24, 24, 24, 0, 0, 0, 0, 0, 0],
    '枣': [26, 49, 49, 49, 26, 49, 49, 0, 0, 0],
    '葡萄': [5, 7, 7, 7, 5, 7, 7, 0, 0, 0]
}


def calculate_min_cost(prices, stocks, demands):
    # 按价格排序
    sorted_goods = sorted(prices.items(), key=lambda x: x[1])

    # 记录每个顾客购买的商品及数量
    customer_purchases = {i: {} for i in range(10)}
    total_cost = 0

    # 遍历每个顾客
    for customer_id in range(10):
        purchased = False
        # 尝试购买单价最低的商品
        for good, price in sorted_goods:
            if demands[good][customer_id] > 0 and stocks[good] > 0:
                # 购买一个单位的商品
                customer_purchases[customer_id][good] = 1
                stocks[good] -= 1
                total_cost += price
                purchased = True
                break
        # 如果没有购买任何商品，则购买单价最高的商品
        if not purchased:
            for good, _ in reversed(sorted_goods):
                if demands[good][customer_id] > 0 and stocks[good] > 0:
                    customer_purchases[customer_id][good] = 1
                    stocks[good] -= 1
                    total_cost += prices[good]
                    break

    return total_cost, customer_purchases


total_cost, purchases = calculate_min_cost(prices, stocks.copy(), demands)
print(f"总花费: {total_cost}")
for cid, goods in purchases.items():
    print(f"顾客 {cid + 1}: {goods}")