C   79
lis max
Guest on 11th February 2023 01:28:38 AM


  1. #include<stdio.h>
  2. int main(){
  3.         int n, i, j, max;
  4.         int w[1005], f[1005], lis[1005];
  5.         while(1){
  6.                 scanf("%d", &n);
  7.                 if(n == 0) break;
  8.                 for(i=0; i<n; i++){
  9.                     scanf("%d %d", &w[i], &f[i]);
  10.                     lis[i] = 2147483640;
  11.                 }
  12.                 lis[n] = 2147483640;
  13.                 max = 0;
  14.                 lis[0] = 0;
  15.                 for(i=n-1; i>=0; i--){
  16.                         for(j=max; j>=0; j--){
  17.                         /*      printf("%d:%d %d\n", j, f[i], lis[j+1]);*/
  18.                                 if(f[i] >= lis[j] && (w[i] + lis[j]) <= lis[j+1]){
  19.                                 /*      printf("[%d]\n", w[i] + lis[j]);*/
  20.                                         lis[j+1] = w[i] + lis[j];
  21.                                         if(j == max) max++;
  22.                                         /*break;*/
  23.                                 }
  24.                         }
  25.                 }
  26.                 printf("%d\n", max);
  27.         }
  28.  
  29.     getchar();
  30.     return 0;
  31. }
Raw Paste

Login or Register to edit or fork this paste. It's free.