背包九讲问题
引言 通过学习背包九讲这个文档,掌握动态规划题目的解决方法。 1 背包问题 有N 件物品和一个容量为V 的背包。第i 件物品的费用(体积)是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。这里每一件物品只能取一次 1.1 思路 根据子问题定义状态,找出状态转移方程。子问题就是:第i件物品是否放入背包。如果不放,那么第i件物品放入背包中的总价值和第i-1件物品放入背包的总价值相当。如果放入背包,也就是求出第i-1件物品放入v-c[i]的背包中时的值与第i件物品的价值的和,得到的就是总价值。 fi=max{fi-1,fi-1]+w[i]} 核心代码如下: 以下代码中,注意i和j的起始遍历位置,从第1行和第1列开始,此时的1表示的就是物品的编号。 //traverse N goods for(int i = 1;i<=N;i++){ for(int j = 1;j<=V;j++){ if(j-C[i]>=0){ f[i][j] = Math.max(f[i-1][j],f[i-1][j-C[i]]+W[i]); }else{ f[i][j] = f[i-1...