人よ、幸福に生きよ

1
def makeChange(coinValueList, change):
2
    """
3
    使用贪心算法找零
4
    coinValueList: 硬币面额列表，假设已排序（从大到小）
5
    change: 需要找零的金额
6
    """
7
    coins = []
8
    for coin in coinValueList:
9
        while change >= coin:
10
            coins.append(coin)
11
            change -= coin
12
    return coins
13

14
# 示例：找零63分，使用面额为[25, 10, 5, 1]的硬币
15
print(makeChange([25, 10, 5, 1], 63))
16
# 输出: [25, 25, 10, 1, 1, 1] (6个硬币)

1
def recMC(coinValueList,change):
2
    minCoins = change
3
    if change in coinValueList:
4
        return 1
5
    else:
6
        for i in [c for c in coinValueList if c <= change]:
7
            numCoins = 1 + recMC(coinValueList,change - i)
8
            if numCoins < minCoins:
9
                minCoins = numCoins
10
    return minCoins
11

12
print(recMC([1,5,10,25],63))

1
def recDC(coinValueList,change,knownResults):
2
    minCoins = change
3
    if change in coinValueList: #递归基本结束条件
4
        knownResults[change] = 1 #记录最优解
5
        return 1
6
    elif knownResults[change] > 0:
7
        return knownResults[change] #查表成功，直接使用最优解
8
    else:
9
        for i in [c for c in coinValueList if c <= change]:
10
            numCoins = 1 + recDC(
11
                coinValueList,
12
                change - i,
13
                knownResults,
14
            )
15
            if numCoins < minCoins:
16
                minCoins = numCoins
17
                #找到最优解，记录到表中
18
                knownResults[change] = minCoins
19
    return minCoins
20

21
print(recDC([1,5,10,25],63,[0]*64))

1
def fib(n: int) -> int:
2
    if n < 0:
3
        raise ValueError("n must be non-negative")
4
    if n <= 1:
5
        return n
6

7
    dp = [0] * (n + 1)
8
    dp[0], dp[1] = 0, 1
9

10
    for i in range(2, n + 1):
11
        dp[i] = dp[i - 1] + dp[i - 2]
12

13
    return dp[n]

1
def fib(n: int) -> int:
2
    if n < 0:
3
        raise ValueError("n must be non-negative")
4

5
    memo = {0: 0, 1: 1}
6

7
    def dfs(k: int) -> int:
8
        if k in memo:
9
            return memo[k]
10
        memo[k] = dfs(k - 1) + dfs(k - 2)
11
        return memo[k]
12

13
    return dfs(n)

1
def dpMakeChange(coinValueList,change,minCoins):
2
    #从1分开始到change逐个计算最小硬币数
3
    for cents in range(1,change + 1):
4
        #初始化一个最大值
5
        coinCount = cents
6
        #减去每个硬币，向后查最小硬币数，同时记录总的最小数
7
        for j in [c for c in coinValueList if c <= cents]:
8
            if minCoins[cents - j] + 1 < coinCount:
9
                coinCount = minCoins[cents - j] + 1
10
        #得到当前最少硬币数，记录到表中
11
        minCoins[cents] = coinCount
12
    #返回最后一个结果
13
    return minCoins[change]
14

15
print(dpMakeChange([1,5,10,21,25],63,[0]*64))

1
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
2
    for cents in range(change + 1):
3
        coinCount = cents
4
        newCoin = 1 #初始化一下新加硬币
5
        for j in [c for c in coinValueList if c <= cents]:
6
            if minCoins[cents - j] + 1 < coinCount:
7
                coinCount = minCoins[cents - j] + 1
8
                newCoin = j #对应最小数量，所减的硬币
9
        minCoins[cents] = coinCount
10
        coinsUsed[cents] = newCoin
11
    return minCoins[change]
12

13
def printCoins(coinsUsed,change):
14
    coin = change
15
    while coin > 0:
16
        thisCoin = coinsUsed[coin]
17
        print(thisCoin)
18
        coin = coin - thisCoin

1
m(i, W) = max {
2
    m(i-1, W),              // 不选第i个宝物
3
    m(i-1, W-wᵢ) + vᵢ      // 选第i个宝物(前提是 wᵢ ≤ W)
4
}

1
#宝物的重量和价值
2
tr = [None,{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]
3
#大盗最大承重
4
max_w = 20
5

6
#初始化二维表格m[(i,w)]
7
m = {(i,w):0 for i in range(len(tr)) for w in range(max_w +1)}
8

9
#逐个填写二维表格
10
for i in range(1,len(tr)):
11
    for w in range(1,max_w + 1):
12
        if tr[i]['w'] > w: #装不下第i个宝物
13
            m[(i,w)] = m[(i-1,w)] #不装第i个宝物
14
        else:
15
            # 不装第i个宝物，装第i个宝物，两种情况下的最大价值
16
            m[(i,w)] = max(m[(i-1,w)],
17
            m[(i-1,w-tr[i]['w'])] + tr[i]['v'])
18

19
print(m[(len(tr)-1,max_w)])

1
tr = {(2,3),(3,4),(4,8),(5,8),(9,10)}
2
max_w = 20
3
# 初始化记忆化表格m
4
# key是(宝物组合，最大重量)，value是最大价值
5
m = {}
6

7
def thief(tr,w):
8
    if tr == set() or w == 0:
9
        m[(tuple(tr),w)] = 0
10
        return 0
11
    elif(tuple(tr),w) in m:
12
        return m[(tuple(tr),w)]
13
    else:
14
        vmax = 0
15
        for t in tr:
16
            if t[0] <=w:
17
                #逐个从集合中去掉某个宝物，递归调用
18
                #选出所有价值中最大值
19
                v = thief(tr-{t},w-t[0]) + t[1]
20
                vmax = max(vmax,v)
21
        m[(tuple(tr),w)] = vmax
22
        return vmax
23

24
print(thief(tr,max_w))