#!/usr/bin/env python

# -*- encoding: utf-8 -*-

'''

Created on JUN 25, 2013

@author: WYE

'''

import ujson

from operator import itemgetter,attrgetter,itruediv

# --/

# 背包算法1：

# 设有M种物品,每种物品都有一个重量及一个价值,同时有一背包,其容量为C,现在从M种物品里选取诺干件,

# 使其重量之和小于等于背包的容量,且价值和为最大.

#

# 说明：

# goodslist ： [[name,weight,value],...]

# bpholdweight ： 背包可容纳的重量

# --/

def bpa1(goodslist,bpholdweight):

newlistpool = [ [list[0],list[1],list[2],itruediv(list[2], list[1])] for list in goodslist]

print(ujson.encode(newlistpool))

sortlistpool = sorted(newlistpool,key=itemgetter(3),reverse=1)

print(ujson.encode(sortlistpool))

remholdweight = bpholdweight

resultlist = []

for name,weight,value,pervalue in sortlistpool:

if weight <= remholdweight:

resultlist.append([name,weight,value,pervalue])

remholdweight = remholdweight - weight

print(ujson.encode(resultlist))

# --/

# 背包算法2：

# 设有M种物品,每种物品都有一个重量及一个价值,同时有一背包,其容量为C,现在从M种物品里选取诺干件,

# 使其重量之和刚好等于背包的容量,且价值和为最大.

#

# 说明：

# goodslist ： [[name,weight,value],...]

# bpholdweight ： 背包可容纳的重量

# --/

def bpa2(goodslist,bpholdweight):

name = [list[0] for list in goodslist]

weight = [list[1] for list in goodslist]

value = [list[2] for list in goodslist]

n = len(goodslist)

k = 0

b = []

r = []

while True:

while bpholdweight > 0 and k < n:

if bpholdweight - weight[k] >= 0:

b.append(k)

bpholdweight -= weight[k]

k += 1

if bpholdweight == 0:

r = [[name[x],weight[x],value[x]] for x in b]

break

if len(b) == 0:

break

k = b.pop()

bpholdweight += weight[k]

k += 1

return r

def getMaxValue(goodslist,bpholdweight):

list_len = len(goodslist)

MaxValueList = []

ValueSum = 0

TheValueSum = 0

for i in range(list_len):

ReturnValList = bpa2(goodslist,bpholdweight)

for list in ReturnValList:TheValueSum += list[2]

if TheValueSum - ValueSum > 0:

ValueSum = TheValueSum

MaxValueList = ReturnValList

goodslist = goodslist[1:]

TheValueSum = 0

return MaxValueList

if __name__ == "__main__":

# --/

# 应用：

# 用户空间装有许多视频文件,但未续费,需将用户空间降级为1G,但最大价值化保留几个视频文件

# 使保留的这几个视频文件大小之和小于或等于1G,且视频播放次数之和最大

# 数据说明：

# ["l123kop",450,90] ： 视频文件"l123kop"大小是450MB,播放次数是90次.

# --/

listpool = [["l123kop",450,90],["l123jkl",50,100],["l123mkl",10,800],["l123iop",76,79],["l123bgh",900,9000]]

listpool1 = [["l123kop",1025,9000000],["l123jkl",1024,100],["l123mkl",1024,800],["l123iop",1024,79],["l123bgh",900,9000]]

listpool2 = [["l123kop",1,1],["l123jkl",1,2],["l123mkl",2,2],["l123iop",4,10],["l123bgh",12,4],["l123bgh",6,3],["l123bgh",50,1000],["l123bgh",7,7]]

bpa1(listpool2,18)

# --/

# 应用：

# 出门远行,考虑带诺干物品,每种物品都有重量和自身的价值,背包可承重18KG.

# 现在需要找到一种方案,使得装入背包的物品总重刚好等于18KG，且价值和为最大

# 数据说明：

# ["A",1,1] ： 物品"A"大小是1kg,价值权重为1.

# --/

List_Pool = [["A",1,1],["B",1,2],["C",2,2],["D",4,10],["E",12,4],["F",6,3],["G",50,1000],["H",7,7]]

bpGoodsList = getMaxValue(List_Pool,18)

print(ujson.encode(bpGoodsList)) # [["B",1,2],["D",4,10],["F",6,3],["H",7,7]]