背包问题(Knapsack problem)
背包问题是一种组合优化问题，为NP-C Problem
描述
给定一组物品，每个物体都有一定的价值和重量。
给定一个可容纳一定重量的背包，在限定容量内，如何选择物体，使得背包内物体价值总和最高。
解决思路
背包问题的经典解法思路是动态规划
遍历给定物体，当物体重量小于等于背包可容纳重量时，判断放入该物体和之前物体哪个带来价值最大，然后考虑是否置换物体。
状态转移方程
图片发自简书App
解题方程(python)
测试数据： 背包容量 c = 10 物品数量 n = 6 物体重量和价值为： w = [2,2,3,1,5,2] v = [2,3,1,5,4,3]
- 求包内可放入最大价值
def get_max_value(c,n,w,v):
#Time O(cn)
#Space O(cn)
dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,c+1):
dp[i][j] = dp[i-1][j]
#状态转移方程
if j >= w[i-1] and dp[i][j] < dp[i-1][j-w[i-1]] + v[i-1]:
dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
return dp[-1][-1]
- To do:背包问题优化
