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

01-背包问题从最大容量开始从后往前遍历背包容量每种物品只能选择一次。物品种类为n背包容量为k。从最大容量开始从后往前遍历背包容量小于当前物品容量的背包大小不遍历即遍历到w[i]即可。1容量不超过k时最大价值为多少dp数组初始化dp[0]*(k1),全部初始化为0表示都可达dp[0]*(k1) 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)]*(k1) 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]*(k1) for i in range(n): for j in range(w[i],k1): dp[j]max(dp[j],dp[j-w[i]]val[i]) return dp[k]