题意：HM先生喜欢吃汉堡，有两种汉堡，每种无限多个，吃完第一种的汉堡一个需要m时间，第二种需要n时间，HM先生饭量很大可以不停的吃，给定一个时间t，在t时间段内希望HM先生吃尽量多的汉堡，并且空余出来的时间要尽量少
分析：是一个只有两种元素的完全背包问题。
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 #define DEBUG 6 const int MAXN = 10000 + 10; 7 int dp[MAXN]; 8 const int INF = 0x3f3f3f3f; 9 int max(int a, int b){ 10 return a>b?a:b; 11 } 12 int main(){ 13 #ifndef DEBUG 14 freopen("in.txt", "r", stdin); 15 #endif 16 int c[2], t; 17 while(scanf("%d%d%d", &c[0], &c[1], &t)!=EOF){ 18 int i, j; 19 for(i=1; i<MAXN; i++) dp[i]=-INF; 20 dp[0]=0; 21 for(i=0; i<2; i++) 22 for(j=c[i]; j<=t; j++) 23 dp[j]=max(dp[j], dp[j-c[i]]+1); 24 j=t; 25 while(dp[j]<0) j--; //比如输入5 5 4 那么dp[4]<0,需要处理 26 printf("%d", dp[j]); 27 if(j!=t) printf(" %d", t-j); 28 printf("\n"); 29 } 30 return 0; 31 }
