程序员小灰
https://www.cxyxiaowu.com/7895.html
https://juejin.im/post/5d37aa1a518825307a2b791e
https://segmentfault.com/a/1190000012829866

大问题的最优解和小问题的最优解存在联系，比如爬楼梯 fn = fn-1+fn-2
缓存表中row代表选择或者不选择(这个通常就10来个) - column代表选择的成本(这个是从0到限定的W) - entry代表总的value
边界情况是first row为初始value，也可以做个全0的dummy row
迭代时考虑如果此时成本小于当前选择的成本 那就不选，否则 则为选和不选两种情况的最大值
用二维数组很方便，容易复盘，虽然每一行都只取决于上一行，可以用一个array来缓存

普通递归 就是直接 fn = fn-1+fn-2 当然可以用哈希表来缓存中间结果，让空间为O(n)，但时间还是2*n，一般n可以到30以上，此时就爆照了，所以一般212=1024，感觉当W不高,N为16左右的时候还可以考虑一下普通递归

不要纠结一行中的数据关系，只要想着迭代的式子后者说和上一行的关系是否正确就可以

加个dummy node好，方便复盘 numlist.insert(0, 0)

import random

def DP_01_bag(numlist,target):
    numlist.insert(0, 0)
    DP = [[0 for i in range(target+1)] for i in range(len(numlist))] # initialize
    for i in range(len(numlist)):
        for j in range(target+1):
            if i == 0:
                if j >= numlist[i]:
                    DP[i][j]=numlist[i]
            else:
                if j<numlist[i]:
                    DP[i][j] = DP[i-1][j]
                else:
                    DP[i][j] = max(DP[i-1][j-numlist[i]]+numlist[i],DP[i-1][j])
    return DP, DP[len(numlist)-1][target]

# # numlist = random.sample(list(range(20)),8)
# # numlist = [13, 8, 0, 19, 4, 7, 14, 10]
# # target = 20


DP, result = DP_01_bag(numlist,target)
print("numlist is :", numlist)
print("target is :", target)
print("result is:", result)

import numpy as np
DP = np.array(DP)
M, N = DP.shape
b = N-1
w = numlist
w_list = []
for i in range(M-1, 0, -1):
    if(DP[i][b] > DP[i - 1][b]):
        b -= w[i];
        print(w[i],i) 
        w_list.append(w[i])

np.sum(w_list)