有点类似完全背包，不过最后的容量必须被充满。

?

dp[i][j]表示在前i个物品中选择容量不超过j的最大价值。

完全背包转移方程：dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i]]+w[i])

这道题目设数组dp[i][j]表示用前j个硬币组成i的种类个数，转移方程：dp[i][j] = dp[i-1][j]+dp[i][j-

a[i]]因为这里求得是解的个数，所以要用加法，完全背包是求某一种情况所以去最大的。（明天实现一下一维数

组）

代码：

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            using namespace std; int a[6] = {0,1,5,10,25,50}; int dp[7500][7]; int main() { int i,j,n; for(i=1; i<=5; i++) dp[0][i] = 1; for(i=1; i<=7490; i++) dp[i][0] = 0; for(i=1; i<=7489; i++) { for(j=1; j<=5; j++) { if(i >= a[j]) dp[i][j] += dp[i][j-1]+dp[i-a[j]][j]; else dp[i][j] = dp[i][j-1]; } } while(cin >> n) { cout << dp[n][5] << endl; } return 0; } 
          
         
        
       
      
     
    
   
  

?

?