完全背包问题 代码(C)

?

?

题目: 有n个重量和价值分别为w,v的物品, 从这些物品中挑选出总重量不超过W的物品, 求所有挑选方案中价值总和的最大值.

*每件物品可以挑选任意多件.

?

动态规划: 每次选取最大的组合, 加入到数组, 第一种时间复杂度O(nW^2), 第二种时间复杂度O(nW).

解法1, max()部分表明, 要么来源于上面, 要么来源于前面.

?

代码:

?

/*
 * 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]; public: void solve() { for (int i=0; i
         
         输出:
         
?
         
?
         
result = 10
 
         
 
         
 
         
为了节约内存, 可以使用一维数组进行求解.
 
         
?
 
         
代码:
 
         
?
 
         
/*
 * 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=3, W=7; int w[MAX_N] = {3,4,2}, v[MAX_N]={4,5,3}; int dp[MAX_N+1]; public: void solve() { memset(dp, 0, sizeof(dp)); for (int i=0; i
                 
                 输出:
                 
?
                 
?
                 
result = 10
 
                 
 
                 
 
                 
?
 
                 
?
 
                 
?
 
                 
 
                 
?
 
                 
?
 
                 
?