#问题:给定一些物品,用matrix表示(质量,价值),有一背包承重为M #求如何装入物品使背包中物品价值最大,以及得出最大价值。可以部分装入 def bufenbeibao(matrix,M): total_value=0 #总价值 take_lst=[0 for _ in range(len(matrix))] #物品表,用0初始化 matrix.sort(key=lambda x:x[1]/float(x[0]),reverse=True) for i in range(len(matrix)): #从最大价值的物品开始判断 if matrix[i][0]<M: #质量小于当前背包容量 total_value+=matrix[i][1] M-=matrix[i][0] #更新总价值 take_lst[i]=1 #更新物品表 else: #如果背包容量小于等于当前物品质量 #就放入部分物品 total_value+=M*matrix[i][1]/float(matrix[i][0]) #总价值/总量=单位价值 #价值加上 剩余填满背包的质量M*当前物品单位价值 take_lst[i]=M/float(matrix[i][0]) #物品百分比(选择的量M/总量) break return matrix,take_lst,total_value matrix=[(100,30),(60,10),(40,20),(120,50)] #(质量,价值) M=240 #背包总容量 sorted_matrix,thing_list,value=bufenbeibao(matrix,M) print("按单位价值从大到小排序后的matrix:",sorted_matrix) print("拿取物品的占比:",thing_list) print("获得物品的总价值为:",value)