文档章节

01背包问题python(使用递归和动态规划)

元禛慎独
 元禛慎独
发布于 2017/02/08 17:38
字数 381
阅读 337
收藏 0

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
 

© 著作权归作者所有

元禛慎独
粉丝 3
博文 209
码字总数 60366
作品 0
朝阳
程序员
私信 提问
动态规划之01背包问题(python实现)

动态规划之01背包问题python实现 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能...

qq_34178562
2018/04/16
0
0
使用Python解决LeetCode算法题

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

郗南枫
04/27
0
0
动态规划法(一)从斐波那契数列谈起

动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,...

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

算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](http://link.springer.com/book/10.1007%2F978-1-4302-3238-4)[**点击链接可进入Springer下载......

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

问题描述: Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equa......

牛奶芝麻
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写个微信飞机大战

这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!...

上海小胖
今天
8
0
关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
7
0
object 类中有哪些方法?

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

happywe
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部