python-tutorial/06_tool/dp_money.py at master · python201cx/python-tutorial

42 lines (35 loc) · 1.51 KB

# -*- coding: utf-8 -*-

"""

@description: 背包问题

"""

class Dp(object):

def __init__(self, money):

self.mark = [0 for _ in range(money + 1)] # 备忘录

self.money = money

def dp(self, money):

self.coin = 0 # 需要的硬币数为0

if self.mark[money] != 0: # 在备忘录中寻找该金额下的最少硬币找零数，若存在，则取出

self.coin = self.mark[money]

elif money <= 0: # 边界问题

if money == 0: # 如果金额为零，则代表刚好算是一种找零方法

self.coin = 0 # 这里的0不是代表硬币数为0，而是代表这种方法可行，因为在下面已经有加1，若是这里coin为1，结果就会比答案多1

else:

self.coin = float("inf") # 若是金额为负数，即“拿多了”，这种方法不可行，则硬币消耗数为无穷大

elif money > 0:

self.coin = min(self.dp(money - 1), self.dp(money - 3), self.dp(money - 5)) + 1 # 递归，找出最少的可以凑齐金额数money的方法

self.mark[money] = self.coin # 做备忘录

return self.coin

def maxsum(inner_list):

Max, temp = inner_list[0], 0

for i in inner_list:

if temp < 0:

temp = i # 更新起点

else:

temp += i

Max = max(temp, Max)

return Max

if __name__ == '__main__':

m = Dp(65) # 找零钱

print(m.dp(10))

print(maxsum([1, -2, 3, 10, -4, 7, 2, -5]))

Navigation Menu