编程算法 - 背包问题(三种动态规划) 代码(C)

背包问题(三种动态规划) 代码(C)

?

?

?

可以用动态规划(Dynamic Programming, DP)求解, 可以通过记忆化搜索推导出递推式, 可以使用三种不同的方向进行求解.

动态规划主要是状态转移, 需要理解清晰.

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; class Program { static const int MAX_N = 100; int n=4, W=5; int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2}; int dp[MAX_N+1][MAX_N+1]; //默认初始化为0 public: void solve() { for (int i=n-1; i>=0; i--) { for (int j=0; j<=W; ++j) { if (j
         
         输出:
         
?
         
?
         
result = 7
 
         
 
         
?
 
         
节省空间, 可以使用1维数组的动态规划.
 
         
代码:





 
         
?
 
         
/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
          
           
#include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 using namespace std; class Program { static const int MAX_N = 100; int n=4, W=5; int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2}; int dp[MAX_N+1]; public: void solve() { memset(dp, 0, sizeof(dp)); for (int i=0; i
                
                 =w[i]; --j) { dp[j] = max(dp[j], dp[j-w[i]]+v[i]); } } printf(result = %d , dp[W]); } }; int main(void) { Program P; P.solve(); return 0; } 
                
               
              
             
            
           
          
 
         
 
         输出: 
         
?
 
         
?
 
         
result = 7
 
         
 
         
 
         
?
 
         
?
 
         
?
 
         
?
 
         
 
         
?
 
         
?
 
         
?
 
         
?