贪心法之背包问题

一、问题描述

果园里正在举办一场装背包问题的比赛，规定每一个参赛者有一个背包，承重为20kg，
参赛者是熊猫，山羊，梅花鹿，给定四种水果，对应的重量和价值为如下所示，规则是：
水果可以装一部分，装入的总重量不能超过背包重量，背包中装入的水果总价值最高者获胜。

物品名称重量（kg）价值（元）
苹果 15 300
香蕉 18 180
橘子 10 150
猕猴桃 9 270

二、代码实现

代码如下：

# -*- coding: utf-8 -*-
"""
Created on Sun Nov 21 12:52:32 2021

@author: lenovo

果园里正在举办一场装背包问题的比赛，规定每一个参赛者有一个背包，承重为20kg，
参赛者是熊猫，山羊，梅花鹿，给定四种水果，对应的重量和价值为如下所示，规则是：
水果可以装一部分，装入的总重量不能超过背包重量，背包中装入的水果总价值最高者获胜。

物品名称     重量（kg）    价值（元）
苹果         15          300
香蕉         18          180
橘子         10          150
猕猴桃        9          270

"""

fuit = [
        {"fuit":"苹果","重量":15,"价值":300},
        {"fuit":"香蕉","重量":18,"价值":180},
        {"fuit":"橘子","重量":10,"价值":150},
        {"fuit":"猕猴桃","重量":9,"价值":270},
        ]

# 字典排序
def dict_sort(dict):
    
    for i in range(len(dict)):
        for j in range(i,len(dict)):
            
            if dict[i]["单位价值"] < dict[j]["单位价值"]:
                temp = dict[i]
                dict[i] = dict[j]
                dict[j] = temp
            

def bag(m,fuit,n):
    
    i = 0
    s = 0
    
    for a in range(n):
        fuit[a]["单位价值"] = fuit[a]["价值"] // fuit[a]["重量"]
    
    dict_sort(fuit)
    
    for a in range(n):
        
        if fuit[a]["重量"] <= m:
            array[a] = 1
            m -= fuit[a]["重量"]
            s += fuit[a]["价值"]
        else:
            s += fuit[a]["单位价值"] * m
            break
        
    
    return s

array = [0,0,0,0]

print(bag(20, fuit, 4))