HDU 4508 湫湫系列故事——减肥记I（完全背包入门）

 1 /***************************
 2 
 3    湫湫系列故事——减肥记I(HDU 4508)
 4    http://acm.hdu.edu.cn/showproblem.php?pid=4508
 5    完全背包入门
 6 
 7 ***************************/
 8 
 9 #include<iostream>
10 #include<cstring>
11 #include<cstdio>
12 using namespace std;
13 typedef long long ll;
14 
15 ll dp[111111];
16 ll a[111],b[111];
17 
18 int main()
19 {
20     ll n,m,i,j;
21     while (~scanf("%I64d%",&n)&&n)
22     {
23         for (i=0;i<n;i++) cin>>a[i]>>b[i];
24         cin>>m;
25         memset(dp,0,sizeof(dp));
26 
27         for (i=0;i<n;i++)   ///完全背包模板
28         {
29             for (j=b[i];j<=m;j++)   ///注意和01背包的区别
30             dp[j]=max(dp[j-b[i]]+a[i],dp[j]);
31         }
32         
33         cout<<dp[m]<<endl;
34     }
35 }