首页 > 其他 > 详细

背包问题

时间:2016-10-21 00:40:09      阅读:131      评论:0      收藏:0      [点我收藏+]

求出将1元,5元,10元,20元凑成n(n>50)的方法的个数,并输出组合结果。

F(N,M)=F(N,M-1)+F(N-VAL[M],M)

F(N,M)表示 用不超过第M个值的数来表示N 的所有组合方案

 

int main()  
{  
    int val[7] = { 0,1,2,5,10,20,50 };  
    int f[101][7];  
    memset(f, 0, sizeof(f));  
      
        for (int j = 0; j <= 6; j++)  
                 f[0][j] = 1;  
          
        for (int j = 1; j <= 6; j++)  
        {  
            for (int i = 1; i <= 100; i++)  
            {  
                if (i - val[j] < 0)  
                    f[i][j] = f[i][j - 1];  
            else  
                    f[i][j] = f[i - val[j]][j] + f[i][j - 1];  
            }  
        }  
      
        cout << f[100][6] << endl;  
        system("pause");  
        return 0;  
    }  

 

背包问题

原文:http://www.cnblogs.com/Lunais/p/5951329.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!