hdu 4508(完全背包）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4508

一开始还以为是一个01背包呢。。。看了第二组测试数据之后就发现是完全背包了。。。

View Code

 1 #include<iostream>
 2 const int N=110;
 3 using namespace std;
 4 int dp[N*N*10];
 5 struct Node{
 6     int a,b;
 7 }node[N];
 8 
 9 int main(){
10     int n;
11     while(~scanf("%d",&n)){
12         for(int i=0;i<n;i++){
13             scanf("%d%d",&node[i].a,&node[i].b);
14         }
15         int m;
16         scanf("%d",&m);
17         memset(dp,0,sizeof(dp));
18         for(int i=0;i<n;i++){
19             for(int j=0;j<=m;j++){
20                 if(j<node[i].b)continue;
21                 dp[j]=max(dp[j],dp[j-node[i].b]+node[i].a);
22             }
23         }
24         printf("%d\n",dp[m]);
25     }
26     return 0;
27 }