动态规划

import numpy as np
from functools import wraps
"""假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 
解法：
　　用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0...n]
，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值"""
"""1.直接自顶向下实现递归式，并将中间结果保存，这叫备忘录法；"""
"""带备忘录的递归方式的优点就是易于理解，易于实现，代码简洁干净，运行速度也不错，直接从需要求解的问题出发，
而且只计算需要求解的子问题，没有多余的计算。但是，它也有自己的缺点，因为是递归形式，所以有限的栈深度是它的硬伤，有些问题难免会出现栈溢出了。"""
from functools import wraps
def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap
@memo
def ccc(total):
    list1 = []
    if total in [1, 3, 5]:
        return 1
    if total > 1:
        list1.append(ccc(total-1))
    if total > 3:
        list1.append(ccc(total-3))
    if total > 5:
        list1.append(ccc(total-5))
    su = min(list1) + 1
    return su
from functools import wraps
def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args[1] not in cache:
            cache[args[1]] = func(*args)
        return cache[args[1]]
    return wrap
@memo
def ca(p, total):
    li = [] 
    if total in p:
         return 1
    else:     
        for i in p:
            if total >= i:
                li.append(ca(p, total-i))      
    s = min(li) + 1
    return s
from functools import wraps
def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args[1] not in cache:
            cache[args[1]] = func(*args)
        return cache[args[1]]
    return wrap
@memo
def ca(p, total):
    mi = total
    if total in p:
         return 1
    for i in p:
        if total >= i:
            count = ca(p, total-i) + 1
            if count < mi:
                mi = count
    return mi
"""2.按照递归式自底向上地迭代，将结果保存在某个数据结构中求解
"""
"""于是，迭代版本的实现方式就诞生了！
迭代实现方式有2个好处：1.运行速度快，因为没有用栈去实现，也避免了栈溢出的情况；2.迭代实现的话可以不使用dict来进行缓存，
而是使用其他的特殊cache结构，例如多维数组等更为高效的数据结构。"""
def bbb(p, v):
    n1 = len(p) + 1
    n2 = v + 1
    s = np.array([[0] * n2] * n1)
    for i in range(1, n1):
        for j in range(min(p), n2):
            list1 = []
            for x in p:
                if j > x and j - x >= min(p):
                    list1.append(s[i, j - x])
                elif j == x:
                    list1.append(0)
            s[i, j] = min(list1) + 1
    return s
import numpy as np
if __name__ == '__main__':
    p = [1, 3, 5]
    v = 10
    s = bbb(p, v)
    print(s)
import copy
def ca(p, v):
    n1 = len(p)
    s = np.array([[0] * n1] * v)
    l1 = {}
    for i in range(v):
        min_count = v
        l1[i] = []
        for j in range(n1):
            if i == p[j]:
                min_count = 1
                l1[i] = []
                l1[i].append(p[j])
            if i > p[j] and s[i-p[j], j] + 1 < min_count:
                    min_count = s[i-p[j], j] + 1
                    l1[i] = copy.copy(l1[i-p[j]])
                    l1[i].append(p[j])
            s[i, j] = min_count
    return s, l1
Min=[x for x in range(12)];
VN=[2,3,5];
for i in range(1,12,1):
    for j in range(3):
        if VN[j]<=i and Min[i-VN[j]]+1<Min[i]:
            Min[i]=Min[i-VN[j]]+1;
print(Min[1::1])
    """这就是递归实现和迭代实现的重要区别：递归实现不需要去考虑计算顺序，只要给出问题，然后自顶向下去解就行；
    而迭代实现需要考虑计算顺序，并且顺序很重要，算法在运行的过程中要保证当前要计算的问题中的子问题的解已经是求解好了的。"""
"""如果当前物品大于背包的容积，这个物品太大了，包塞不下。那么最优解就是前n-1件物品放进这个背包的最大价值。
arr[i][j] = arr[i-1][j]
如果当前物品不大于背包的容积，这个物品可以塞下，需要重新开始计算，当前 i 物品组合的最大价值。分为两种情况，该物品放还是不放。
2.1 不放的话，和上面的公式相同；  
2.2 放的话，则背包容量减去第n件物品的重量，再去装前 i-1 件物品，所得的最大价值。两种情况中较大的就是最优解。
arr[i][j] = max (arr[i-1][j] , arr[i-1][j -v[i]]+ cost[j])
一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
"""
"""m个物品价值为 p[m]，体积为 w[m]，现有一个容量为 v 的背包，怎么装物品价值最大?"""
def kkk(p, w, v):
    n1 = len(p) + 1
    n2 = v + 1
    s = np.array([[0] * n2] * n1)
    # for x in range(n2):
    #   s[0, x] = x
    for i in range(1, n1):
        # s[i, 0] = p[i-1]
        for j in range(1, n2):
            if p[i-1] > j:
                s[i, j] = s[i-1, j]
            else:
                s[i, j] = max(s[i-1, j], s[i-1, j-p[i-1]] + w[i-1])
    return s
p = [3, 2, 9, 4, 3]
w = [700, 500, 800, 600, 520]
v = 8
c = kkk(p, w, v)
import copy
length = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
profit = (1, 5, 8, 9,10, 17, 17, 20, 24, 30)
n = 20
def ddd(length, profit, n):
    dic = {}
    dic[0] = []
    s = [0] * (n)
    for i in range(1, n):
        ma = -1
        for j in range(len(length)):
            y = s[i-length[j]] + profit[j]
            if i >= length[j] and y > ma:
                ma = y
                dic[i] = []
                dic[i] = copy.deepcopy(dic[i-length[j]])
                dic[i].append(length[j])
        s[i] = ma
    return s, dic

// 扔鸡蛋问题 解析
func main(){
    floors := 100
    eggs := 2
    dp := [3][101]int {}
    // 外面这两层循环（循环鸡蛋数量和楼层数量）是为了将dp二维数组的每一个值遍历到
    for egg:=1; egg < eggs+1; egg++ {
        for floor:=1; floor < floors + 1; floor++ {
            // 解决这样的干扰非常有必要，把底层边界进行固定，最大程度防止 0， 1的错误
            // 这步判断是解决掉 最初状态的干扰，鸡蛋只有一个
            if egg == 1{
                dp[1][floor] = floor
                continue
            }
            // 这两部判断是解决掉 最初状态的干扰，只有一层楼的状态
            if floor == 1{
                dp[egg][1] = 1
                continue
            }
            tmpMin := floors
            // 这一层遍历是进行状态转移核心，限定了当前的 egg和floor时
            // 通过遍历当前floor 之前的已知解，从中取出最优方案
            for sonFloor:=1; sonFloor < floor; sonFloor++ {
                tmpMax := 0
                // dp[egg][floor-sonFloor] 鸡蛋没碎，考虑剩下几层楼所需要的最优解
                // 
                if dp[egg][floor-sonFloor] <= dp[egg-1][sonFloor-1] {
                    tmpMax = dp[egg-1][sonFloor-1] + 1
                } else {
                    tmpMax = dp[egg][floor-sonFloor] + 1
                }
                if tmpMax < tmpMin {
                    tmpMin = tmpMax
                }
            }
            dp[egg][floor] = tmpMin
        }
    }
    fmt.Println(dp)
    fmt.Println(dp[eggs][floors])
}