01package

题目描述

题目链接: POJ3624
很经典的01背包问题，不累述了。

理解

01背包问题本身代码并不复杂，很难理解的是状态的转移，引用Tanky Woo的一句话

首先说下动态规划，动态规划这东西就和递归一样，只能找局部关系，若想全部列出来，是很难的，比如汉诺塔。你可以说先把除最后一层的其他所有层都移动到2，再把最后一层移动到3，最后再把其余的从2移动到3，这是一个直观的关系，但是想列举出来是很难的，也许当层数n=3时还可以模拟下，再大一些就不可能了，所以，诸如递归，动态规划之类的，不能细想，只能找局部关系。

使用01背包问题这类简单的问题来学习动态规划是新手友好的。

其次，对于01背包进行一维数组的优化，以及和完全背包问题及其一维数组优化的对比， 能够更好的理解状态这个概念。

原始版本

for(int i = 1; i <= nItem; i++)
{
    for(int j = 1; j <= nWeight; j++)
    {
        //如果不选一件物品有两种可能：
        //1. 装不下
        //2. 不想装
        if(j < weight[i])
            dp[i][j] = dp[i - 1][j];
        else{
            //注意此处max函数中dp数组无论拿还是不拿都是从[i - 1]的状态转移而来的
            //[i - 1]保证此处为01背包问题
            //即保证每个物品只有一个
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
}

使用一维数据进行优化

当nItem比较小(例如在1000以内)时，使用二维数组是可以使用的，但当nItem偏大(n为10000)时， 使用二维数组时不可行的， 所以学会使用一维数组是必须的。

  for(int i = 1; i <= nItem; i++)
  {
//此处的j为逆序
//说明每次计算得出的dp[j]都是从nItem - 1转移(保证每件物品只选一次)而来的
//完全背包与这个有微小的区别
//即从nItem转移而来的(每件物品可选任意次)
      for(int j = nWeight; j >= 1; j--)
      {
          if(weight[i] > j)
              continue;
          dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
      }
  }

参考链接

Tanky Woo’s Blog
DD大牛的背包九讲
北大动归相关课件

本人文笔略拙，觉得本文晦涩难懂可参考以上大牛的相关文档。