01背包

先看问题：有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

因为背包就是要往里面放东西，所以一件物品就是有放或不放两种情况，怎么才能判断当前物品该不该放进去从而使利益最大化。

首先，我们用i代表前i件物品，v代表包的最大承重，ci是第i件物品的重量、wi是第i件物品的价值、f[i,j]是最大价值(i个物品放入有j个空间的包)。

第一种情况：第i件不放进去，这时所得价值(f[i][j])为:f[i][j]=f[i-1][v]，即当前价值(f[i][j])为前i-1个物品的价值f[i-1][v]：当前i个物品用j个空间所拥有的价值就等于前i-1个物品用j个空间的价值。

另一种情况：第i件放进去，这时所得价值为:f[i][j]=f[i-1][v-c[i]]+w[i]，则当前价值(f[i][j])不是前i-1个物品的价值f[i-1][v]，包内的空间就不是v了，而应该是v-c[i]（即应该是在满足放入第i个物品空间的前提下），而是继承前i-1个物品占用体积为v-c[i]时的价值，再加上加上当前物品价值wi。

于是，对于第i件物品就是这两种操作，而你又想要最大价值，所以：f[i][j]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])

代码：

for (int i=1;i<=n;++i) {　
     for (int j=v;j>=0;--j) {
        if(c[i]<=j)//如果当前物品可以放入当前空间的背包
           f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
        else 
           f[i][j]=f[i-1][j];//如果当前物品放不进去，那么继承前i个物品在当前空间大小时的价值
　　　}
}

举例：

有5件物品和一个容量为10的背包，物件的重量和价值如下：

优化：滚动数组

从上面计算f[i][j]可以看出，在计算f[i][j]时只使用了f[i-1][0……j]，所以说并没有使用其他子问题，所以说在存储子问题解的时候，只用存储f[i-1]的子问题解即可；所以说可以用一个一维数组替换掉那个二维数组，一个存储子问题，一个存储正在解决的子问题。我们用f[v]表示当前状态是容量为v的背包所得价值

优化代码:

for (int i=1;i<=n;++i) {
    for (int j=v;j>=0;--j) {
        if(c[i]<=j)
           f[j]=max(f[j],f[j-c[i]]+w[i]);
        else 
           f[j]=f[j];
     }
}