0-1背包问题（递归实现）

#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; /* *0-1背包问题（递归实现） */ //int * * values;//values[i][j]表示在前i个物品中能够装入容量为j的背包中的物品的最大值 (二维数组方案一) vector
        
         > values;//values[i][j]表示在前i个物品中能够装入容量为j的背包中的物品的最大值 (二维数组方案二) int knapsack(vector
         
          & w,vector
          
           & v,int i,int vol) { if(i==0||vol==0) return values[i][vol] = 0; if(vol
           
            =w[i]) { int fi = knapsack(w,v,i-1,vol); int se = knapsack(w,v,i-1,vol-w[i])+v[i]; return values[i][vol] = max(fi,se); } } void PrintRes(vector
            
             & w,int i,int vol) { if(i<=0) return ; if(values[i][vol]>values[i-1][vol]) { PrintRes(w,i-1,vol-w[i]); cout<
             
               w;//物品的重量 vector
              
                v;//物品的价值 int vol; w.push_back(0);// v.push_back(0);// copy(istream_iterator
               
                (cin),istream_iterator
                
                 (),back_inserter(w)); cin.clear(); cin.sync(); copy(istream_iterator
                 
                  (cin),istream_iterator
                  
                   (),back_inserter(v)); cin.clear(); cin.sync(); cin>>vol; //创建和初始化v数组 /*values = new int*[w.size()]; (二维数组方案一) for (int i = 0; i < w.size(); i++) { values[i] = new int[vol+1]; }*/ //(二维数组方案er) values = vector
                   
                    >(w.size(),vector
                    
                     (vol+1)); //运行查找解决方案的函数 knapsack(w,v,w.size()-1,vol); //输出0-1背包结果
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   
	PrintRes(w,w.size()-1,vol);
}

输入示例：

第一行输入各个物品的重量

第二行输入各个物品的价值

第三行输入背包的最大承受重量