## 01背包问题python（使用递归和动态规划） 原

元禛慎独

1、使用递归方法

yuanzhen@ubuntu:~/P_script\$ cat mine_dp_1.py
#!/usr/bin/env python

def get_file(file_in):
fd_list=[]
f_in=open(file_in,"r")
for l_raw in f_in:
line=l_raw.strip().split(" ")
fd_list.append([int(x) for x in line]);
f_in.close()
return fd_list

def init(fd_list):
pNeed_list=[]
Gold_list=[]
for p,g in fd_list[1:]:
pNeed_list.append(p)
Gold_list.append(g)
return pNeed_list, Gold_list

def getMaxGold(people, mineNum):
if (people, mineNum) in set(sumGold.keys()):
retgold=sumGold[(people,mineNum)]

elif mineNum==0:
if people>=peopleNeed[mineNum]:
retgold=Gold[mineNum]
else:
retgold=0
else:
if(people>=peopleNeed[mineNum]):
retgold=max(getMaxGold(people,mineNum-1), getMaxGold(people-peopleNeed[mineNum], mineNum-1)+Gold[mineNum])
else:
retgold=getMaxGold(people,mineNum-1)
sumGold[(people, mineNum)]=retgold
return retgold

def main():
file_in="/home/yuanzhen/P_script/01beibao/beibao0.in"
fd_list=get_file(file_in)
print fd_list
peopleTotal=fd_list[0][0]
mine=fd_list[0][1]
global sumGold, peopleNeed, Gold
sumGold={}
peopleNeed,Gold=init(fd_list)
print peopleTotal, mine
print peopleNeed
print Gold
maxgold=getMaxGold(peopleTotal, mine-1)
print maxgold

main()
#################################

2、动态规划方法

yuanzhen@ubuntu:~/P_script\$ cat mine_dp_2.py
#!/usr/bin/env python

def get_file(file_in):
fd_list=[]
f_in=open(file_in,"r")
for l_raw in f_in:
line=l_raw.strip().split(" ")
fd_list.append([int(x) for x in line]);
f_in.close()
return fd_list

def init(fd_list):
pNeed_list=[]
Gold_list=[]
for p,g in fd_list[1:]:
pNeed_list.append(p)
Gold_list.append(g)
return pNeed_list, Gold_list

def getMaxGold(people, mine):
for people_i in range(0,people+1):
for mine_j in range(mine+1):
people_num=peopleNeed[mine_j]
if mine_j==0:
if people_i>=people_num:
sumGold[(people_i, mine_j)]=Gold[mine_j]
else:
sumGold[(people_i, mine_j)]=0
else:
if people_i>=people_num:
sumGold[(people_i, mine_j)]=max(sumGold[(people_i-people_num, mine_j-1)]+Gold[mine_j], sumGold[(people_i,mine_j-1)])
else:
sumGold[(people_i, mine_j)]=sumGold[(people_i, mine_j-1)]
return sumGold[(people, mine)]

def main():
file_in="/home/yuanzhen/P_script/01beibao/beibao0.in"
fd_list=get_file(file_in)
print fd_list
peopleTotal=fd_list[0][0]
mine=fd_list[0][1]
global sumGold, peopleNeed, Gold
sumGold={}
peopleNeed,Gold=init(fd_list)
print peopleTotal, mine
print peopleNeed
print Gold
maxgold=getMaxGold(peopleTotal, mine-1)
print maxgold

main()
########################################

[[100, 5], [77, 92], [22, 22], [29, 87], [50, 46], [99, 90]]
100 5
[77, 22, 29, 50, 99]
[92, 22, 87, 46, 90]
133

### 元禛慎独

qq_34178562
2018/04/16
0
0

Github仓库地址: https://github.com/coolboygym/leetcode-python 本仓库主要记录自己在LeetCode上AC的代码，全部使用Python实现。 其中一些代码参考了评论区中的高票回答，在代码中给出了参...

04/27
0
0

jclian91
2018/05/28
0
0
Python算法设计总结篇

2014/07/06
967
2
【DP、Greedy】416. Partition Equal Subset Sum

06/05
0
0

CQRS与AXON

CQRS 看了蛮多文章，只会CRUD，却不懂CQRS，CQRS是遵循DDD思想而产生的一种模式，Command and Query Responsibility Segregation 命令与查询隔离。查询就直接通过正常的模式service调dao层。...

37分钟前
4
0
OSChina 周三乱弹 —— 欢迎你来做产品经理

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @巴拉迪维 ：10多次劲歌金曲获奖，更多叱咤歌坛排名，黎明才应该是四大天王之首，只可惜拍的电影太少。单曲循环一个多月的歌，力荐 《无名份的...

52分钟前
118
8
500行代码，教你用python写个微信飞机大战

8
0

shzwork

7
0
object 类中有哪些方法？

getClass(): 获取运行时类的对象 equals()：判断其他对象是否与此对象相等 hashcode()：返回该对象的哈希码值 toString()：返回该对象的字符串表示 clone()： 创建并返此对象的一个副本 wait...

happywe

7
0