【算法与数据结构】——动态规划（1）
经典01背包问题
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
状态转移方程
dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]
dp[i][j] = dp[i-1][j] //j < w[i]
由上述状态转移方程可知，dp[i][j]的值只与dp[i-1][0,…,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。需要注意的是，为了防止上一层循环的dp[0,…,j-1]被覆盖，循环的时候 j 只能逆向枚举（空间优化前没有这个限制），伪代码为：
// 01背包问题伪代码(空间优化版)dp[0,...,W] = 0for i = 1,...,Nfor j = W,...,w[i] // 必须逆向枚举!!!dp[j] = max(dp[j], dp[j−w[i]]+v[i])
完全背包
问题：给定n种物品，每种物品都有重量wi和价值vi，物品数量没有限制。背包容量为W，求解在不超过背包容量的情况下如何放置物品，使背包中物品的价值之和最大。
发话少说上代码：
for(int i = 1;i <= n;i++){for(int j = w[i];j <= W;j++)//正序循环{dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}
谁借莪１个温暖的怀抱￠
àì夳堔傛蜴生んèń
柔情只为你懂
朱雀
我会带着你远行
还没有评论，来说两句吧...