01背包问题;

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

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

F[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]};f[i-1][v-c[i]]+w[i]表示在第i-1个背包在v-c[i]的容量下的价值+第i件物品的价钱。

在背包问题中，时间为O(NV)没办法优化，但是在空间上是可以优化的。可以这样考虑，每件f[i][v]只跟他的f[i-1][0……v]有关系，那么因为i只和自己的i-1有关，所以只需要更新[0……v]就行了。又f[v]只和[0……v]有关，所以在实现策略的时候就可以一下的策略。

For i =1 to n

  For V=v to 0

     F[V]=max{f[V],f[V-c[i]]+w[i]};

优化，对于i物品来说，v<c[i]是放不下去的，所以第二个循环可以改为for V=v to c[i];

初始化问题：

当不需要把背包装满的时候，f[0……V]=0;因为最后的结果在f[v]中，f[v]表示前第i个物品放入一个容量为V的背包的最大价值。当初始条件为上试的时候，背包是正确的。

当需要装满的时候f[0]=0,f[1……V]=-INF，很容易理解，f[V]表示在0个物品放入时容量为v的背包的最大价值，这是由于要满足装满这个条件。由于由于没有东西所以只只有v=0,满足价值为0，其他不合法。

完全背包问题

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

对于这种情况有这样一种转移方程，

F[v]=max{f[v-c[i]]+w[i],i=0…N}

可以这样的理解，对于容量为v的背包的最大值是{f[v-c[i]]容量的背包+w[i]}的最大值。

讨论初始状态，当要求装满的情况下f[0]=0;f[1……v]=-INF；

在不要求装满的情况下f[0……v]=0;

多重背包问题

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

基本的思想是装化成为01背包问题求解

对这个思想进行优化，这时可以看到如此的情况吧n[i]的值拆分成1,2，2^2,……2^k，n[i]-2^k.

并且他们的和都为n[i],这时用这些数和w[i]相乘，这是有一个好处就在与，这些数的加和一定可以构成1……n[i]个物品都出现在dp的过程中。这时时间的复杂度就降低到O(V*Σlog n[i])了。

混合多重背包问题

01和完全背包混合问题。

在这种时候，就是分开处理两类问题先后都对最后的结果没有直接的影响。

在处理01和完全和多重三个问题

因为多重问题和01问题在转化后实际是一样的，其实也可以分开处理。