动态规划——01背包问题、完全背包（python、一维DP）

01-背包问题：从最大容量开始，从后往前遍历背包容量

每种物品只能选择一次。物品种类为n，背包容量为k。从最大容量开始，从后往前遍历背包容量，小于当前物品容量的背包大小不遍历，即遍历到w[i]即可。

（1）容量不超过k时，最大价值为多少

dp数组初始化：dp=[0]*(k+1),全部初始化为0，表示都可达

dp=[0]*(k+1) for i in range(): for j in range(k,w[i]-1,-1): dp[j]=max(dp[j],dp[j-w[i]]+val[i]) return dp[k]

（2）容量恰好为k时，最大价值为多少，如果不能恰好为k，则表示不可达，不可行

dp初始化：dp=[float('-inf')]，初始化为负无穷大，表示为不可达

dp[0]=0容量为0时，一定可达

dp=[float('-inf')]*(k+1) for i in range(): for j in range(k,w[i]-1,-1): dp[j]=max(dp[j],dp[j-w[i]]+val[i]) if dp[k]==float('-inf'): print(0) return 0 else: print(dp[k]) return dp[k]

完全背包问题：从前往后遍历背包容量

每种物品可以选择无限多次。物品种类为n种。

dp=[0]*(k+1) for i in range(n): for j in range(w[i],k+1): dp[j]=max(dp[j],dp[j-w[i]]+val[i]) return dp[k]