HDOJ 2159 FATE

二维背包，既有耐性度限制又有怪兽的个数的限制，每种怪兽是无限多个就说明是二维的无限背包。
 

代码：

[cpp] 
#include<iostream> 
using namespace std; 
int a[105],b[105],dp[105][105]; 
int main() 
{ 
    int n,m,k,s,i,j,l; 
    while( scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){ 
           for( i=0; i<k; i++) 
                scanf("%d%d",&a[i],&b[i]); 
                 
           memset(dp,0,sizeof(dp));      
           for( i=0; i<k; i++) 
            for( j=b[i]; j<=m; j++) 
             for( l=1; l<=s; l++) 
                  dp[j][l]=max(dp[j][l],dp[j-b[i]][l-1]+a[i]); 
            
           bool flag=false;   
           for( i=0; i<=m&&!flag; i++){ 
            for( j=0; j<=s&&!flag; j++){ 
                 if( dp[i][j]>=n){ 
                     flag=true;  
                     printf("%d\n",m-i); 
                 } 
            } 
           } 
           if( !flag) 
               printf("-1\n"); 
     } 
     return 0; 
} 

 作者：aacm1992

补充：软件开发 , C++ ,

上一个：C++学习笔记（八） 智能指针
下一个：hive数据导入