哈理工1053完全背包

顺序求解是完全背包，逆序求解是0-1背包，自己想想
View Code
 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 struct node
 5 {
 6     int cost,value;
 7 } ;
 8 node u[100005];
 9 int f[100005];
10 int main()
11 {
12     int G,U;
13     int T,cur;
14     scanf("%d",&T);
15     while(T--)
16     {
17 //        freopen("in.cpp","r",stdin);
18         scanf("%d%d",&G,&U);
19         memset(f,0,sizeof(f));
20         cur =0;
21         for(int i=0; i<G; i++)
22         {
23             u[i].cost = 1000000;
24             u[i].value = -10000;
25         }
26         for(int i=0; i<U; i++)
27         {
28             int v,c;
29             scanf("%d%d",&v,&c);
30             if(c > G) continue;
31             for(int j = 0; j<= cur; j++)
32             {
33                 if(u[j].value < v && u[j].cost >= c)
34                 {
35                     if(u[j].value < 0) cur++;
36                     u[j].value = v;
37                     u[j].cost = c;
38                     break;
39                 }
40             }
41         }
42         for(int i=0; i < cur; i++)
43             for(int j=1; j <= G; j++)
44             {
45                 if(j- u[i].cost >=0 && f[j-u[i].cost] + u[i].value > f[j])
46                     f[j] = f[j-u[i].cost] + u[i].value;
47             }
48         printf("%d\n",f[G]);
49     }
50     return 0;
51 }