fork download
copy 
  1. #include<cstdio>
  2.  
  3. struct node
  4. {
  5.     int value,weight;
  6. };
  7. int weight[109],val[109];
  8. node dp[501][101];
  9.  
  10. int main()
  11. {
  12.  //   char c;
  13.    // scanf("%c",&c);
  14.     int w,n;
  15.     while(scanf("%d%d",&w,&n)==2)
  16.     {
  17.         if(w==0&&n==0)
  18.             break;
  19.  
  20.         for(int i=0;i<n;i++)
  21.         {
  22.             scanf("%d%d",&weight[i],&val[i]);
  23.         }
  24.         for(int i=0;i<=w;i++){
  25.             dp[0][i].value=0;
  26.             dp[0][i].weight=0;
  27.         }
  28.         for(int i=0;i<=n;i++)
  29.         {
  30.             dp[i][0].value=0;
  31.             dp[i][0].weight=0;
  32.         }
  33.         for(int i=1;i<=n;i++)
  34.         {
  35.             for(int j=1;j<=w;j++)
  36.             {
  37.                 if(j<weight[i-1])
  38.                     dp[i][j]=dp[i-1][j];
  39.                 else
  40.                 {
  41.  
  42.                     if((dp[i-1][j].value)>(val[i-1]+dp[i-1][j-weight[i-1]].value))
  43.                     {
  44.                         dp[i][j]=dp[i-1][j];
  45.                     }
  46.                     else if((dp[i-1][j].value)<(val[i-1]+dp[i-1][j-weight[i-1]].value))
  47.                     {
  48.                         dp[i][j].value=val[i-1]+dp[i-1][j-weight[i-1]].value;
  49.                         dp[i][j].weight=weight[i-1]+dp[i-1][j-weight[i-1]].weight;
  50.                     }
  51.                     else
  52.                     {
  53.                         if(dp[i-1][j].weight<=weight[i-1]+dp[i-1][j-weight[i-1]].weight)
  54.                         {
  55.                             dp[i][j]=dp[i-1][j];
  56.                         }
  57.                         else
  58.                         {
  59.                              dp[i][j].value=val[i-1]+dp[i-1][j-weight[i-1]].value;
  60.                              dp[i][j].weight=weight[i-1]+dp[i-1][j-weight[i-1]].weight;
  61.                         }
  62.  
  63.                     }//else
  64.  
  65.                 }//else
  66.             //    printf("%d %d  ",dp[i][j].value,dp[i][j].weight);
  67.             }//jloop
  68.            // printf("\n");
  69.         }//iloop
  70.  
  71.         printf("%d %d\n",dp[n][w].weight,dp[n][w].value);
  72.      //   scanf("%c",&c);
  73.     }
  74. }
  75.  
Success #stdin #stdout 0s 3856KB
comments (?)
stdin
copy 
78 20 
24 6 
24 8 
13 0 
23 5 
5 10 
12 3 
14 1 
12 5 
10 9 
21 10 
20 5 
20 2 
11 10 
13 8 
11 1 
10 7 
13 7 
8 2 
24 9 
20 0
 
0 0
stdout
copy 
74 56
https://ideone.com/ZVr6CX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!