0-1背包问题描述

　　有一个窃贼在偷窃一家商店时发现有n件物品，第i件物品价值为v_i元，重量为w_i，假设v_i和w_i都为整数。他希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。他应该带走哪几样东西？

0-1背包问题中：每件物品或被带走，或被留下，（需要做出0-1选择）。小偷不能只带走某个物品的一部分或带走两次以上同一个物品。

比较好的介绍博客： 

　　http://www.importnew.com/13072.html

　　http://blog.csdn.net/wangyuquanliuli/article/details/46628357

　　http://www.cnblogs.com/fly1988happy/archive/2011/12/13/2285377.html

0-1背包问题解决方法

　　0-1背包问题是个典型举办子结构的问题，但是只能采用动态规划来解决，而不能采用贪心算法。因为在0-1背包问题中，在选择是否要把一个物品加到背包中，必须把该物品加进去的子问题的解与

不取该物品的子问题的解进行比较。这种方式形成的问题导致了许多重叠子问题，满足动态规划的特征。动态规划解决0-1背包问题步骤如下：

0-1背包问题子结构：选择一个给定物品i，则需要比较选择i的形成的子问题的最优解与不选择i的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

0-1背包问题递归过程：设有n个物品，背包的重量为w，C[i][w]为最优解。即：

                                       

实现代码如下： 空间复杂度还可以简化为 v+1 而不是原来的(n+1)*(v+1) 。因为每次计算其实所需要的数据都是上一组数组，所以不需要记住前面的很多组数。

#include 
     
      #include 
      
       using namespace std;const int MIN=0x80000000;const int N=3;   //物品数量const int V=5;  //背包容量int f[N+1][V+1];int Package(int *W,int *C,int N,int V);void main(int argc,char *argv[]){ int W[4]={
   0,7,5,8};      //物品权重 int C[4]={
   0,2,3,4};      //物品大小 int result=Package(W,C,N,V); if(result>0) {  cout<
       
        f[i-1][j-C[i]]+W[i])?f[i-1][j]:(f[i-1][j-C[i]]+W[i]);   cout<<"f["<
        <<"]["<
         
          <<"]="<
          
           <