0-1背包问题

链接

https://www.acwing.com/problem/content/2/

题解

选还是不选的问题 定义状态矩阵dp[][] 定义物品体积v[] 定义物品价值w[]

dp[i][j]的含义：前i个物品，背包容量为j的大小时，取得的最大的总价值

当选择第i个物品时物品总价值： dp[i][j-v[i]]+w[i] 当不选择第i个物品时物品总价值： dp[i-1][j] dp[i][j]的最大物品总价值 = max(选,不选)

即 dp[i][j] = max( dp[i][j-v[i]]+w[i] ,dp[i-1][j])