不多讲，dd大牛的背包九讲如此之经典我们只能慢慢体会了：

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

状态转移方程：

1:f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);

2:

for(i=0;i
     
      =c[i];v--)   {       f[v]=max(f[v],f[v-c[i]]+w[i]);    }}
     

　自己的理解：　01背包的主要思想是对于这件物品做出选与不选的决定；将空间优化后V必须是逆序的，因为这样才能保证将当前的第i个物品放进去的时候，f[v]由前一状态的f[v],f[v-c[i]]+w[i]推得且前一状态必须保证从未出现过第i个物品的放于不放问题，因为每种物品只有一件。（完全背包就是顺序了因为每种物品是无限个的）

预处理：粘贴dd大牛的，

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

实现代码：

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; const int max_s = 1007; int v[max_s],w[max_s],f[max_s]; int main() {
    int t,i,j,n,V;     scanf("%d",&t); while(t--)     {
            memset(f,0,sizeof(f));         scanf("%d%d",&n,&V); for(i=0;i
          
           =v[i];j--)             f[j]=max(f[j],f[j-v[i]]+w[i]);         }         printf("%d\n",f[V]);     } return 0; }
          
         
        
       
      

二维01背包记录选择的物品：

#include 
      
       #include 
       
        #include 
        
         #define maxn 22#define N 10007using namespace std;int w[maxn];int f[maxn][N];int L,n;int mk[maxn];//用来标记是否被选void init(){    int i,j;    for (i = 0; i < maxn; ++i)    {        mk[i] = 0;        for (j = 0; j < N; ++j)        f[i][j] = 0;    }}int main(){    int i,j;    //freopen("d.txt","r",stdin);    while (~scanf("%d",&L))    {        scanf("%d",&n);        for (i = 1; i <= n; ++i) scanf("%d",&w[i]);        init();        for (i = 1; i <= n; ++i)        {            for (j = 1; j <= L; ++j)            {                if (w[i] <= j)                {                    if (f[i - 1][j - w[i]] + w[i] > f[i - 1][j])                    f[i][j] = f[i - 1][j - w[i]] + w[i];                    else                    f[i][j] = f[i -1][j];                }                else f[i][j] = f[i - 1][j];            }        }        int Max = 0,e;        for (i = 1; i <= L; ++i)        {            if (Max < f[n][i])            {                Max = f[n][i];                e = i;            }        }        for (i = n; i >= 1; --i)        {            if (f[i][e] == f[i - 1][e - w[i]] + w[i])            {                e -= w[i];                mk[i] = 1;            }            else mk[i] = 0;        }        for (i = 1; i <= n; ++i)        if (mk[i]) printf("%d ",w[i]);        printf("sum:%d\n",Max);    }    return 0;}
        
       
      

 空间优化的记录物品选择开数组num[i][j]记录i状态是否选择j

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include