动态规划--背包

This is my blog.
（未完待续）
动态规划中有一分块，便是背包问题。包括01背包，完全背包，多重背包，分组背包等问题。（此文会随着我学习的进度，逐步更新完成）。本文将会讲述如何去做，并附上此类题型的题目（我做过的）。在学习动态规划之时，可以练习noip noi中的题目。

01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

首先要确定状态，即知道了什么就可以可以知道目前的最大价值。f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。
然后确定状态转移方程。接下来变分为两种情况，第i个物品放与不放。

1.不放当前物品 f[i][j] = f[i-1][j]
2.放当前物品 f[i][j] = f[i-1][j-c[i]]+w[i]
所以结果变为f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}

但是01背包还没有完，它还可以更简化（减少空间）

我们可以知道前i个物品的最大价值，只和前i-1个物品的最大价值有关，和i-2无关，所以只需要开f[2][n]大的数组即可。

在初期的学习中，可以用excel画一下表格，看一下数组是怎么更新的。我们会发现，容量为j的只和比j小的有关，那么如果我们从j=n开始，逐渐减小来更新数组的话，即只需一维数组即可。

for ( i = 1 ; i <= n; i++ ){
      for (j=m; j>=c[i]; j--)
          if (f[j-c[i]] + w[i] > f[j])
               f[j] = f[j-v[i]] + w[i];
}

NASA的食物计划

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci ，价值是 Wi 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

1.状态 f[i, j ] 依然表示前 i 种物品恰放入一个容量为 v的背包的最大权值。
2.转移 f [i,j] = max（f [i -1,j-kc[i] ] + k w[i]) (0 <= k*c[i] <= j)

k要循环吗？这样肯定会超限啊。我们来观察一下表格，如果我们的j是从小到大算的话，那是不是就会有重复加的情况了。仔细分析一下就可知道这可行！

for ( i = 1 ; i <= n; i++ ){
     for (j=c[i]; j<=m; j++)
         if (f[j-c[i]] + w[i] > f[j])
             f[j] = f[j-c[i]] + w[i];
}