SHARE
TWEET

Untitled

a guest Jan 25th, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. using namespace std;
  3. #define MAX_N 102
  4. #define MAX_W 1002
  5.  
  6. int card_w[MAX_N],possiblity[MAX_N*MAX_W] = {0} ,prev[MAX_N*MAX_W] = {0};
  7.  
  8. int main(){
  9.   int wnf,n;
  10.   scanf("%d",&wnf);
  11.   scanf("%d", &n);
  12.   int sum = 0;
  13.  
  14.  
  15.   for(int i = 0;i < n; i++){
  16.     scanf("%d",&card_w[i]);
  17.     sum += card_w[i];
  18.   }
  19.  
  20.  
  21.  
  22.  
  23.   possiblity[0] = 1;
  24.   prev[0] = -1;
  25.  
  26.   for(int j = n - 1;j >= 0; j--){
  27.     for(int i = sum - wnf;i >= card_w[j]; i--){
  28.  
  29.       if(possiblity[i - card_w[j]] != 0){
  30.         possiblity[i] += possiblity[i - card_w[j]];
  31.  
  32.         if(prev[i] == 0) {
  33.           prev[i] = j + 1;
  34.         }
  35.  
  36.  
  37.       }
  38.     }
  39.   }
  40.  
  41.   if(possiblity[sum - wnf] > 1)  {
  42.     printf("-1\n");
  43.   }else if(possiblity[sum - wnf]==0)  {
  44.     printf("0\n");
  45.   }else{
  46.     int iter = sum - wnf;
  47.     while(iter != 0){
  48.       printf("%d ", prev[iter]);
  49.       iter -= card_w[prev[iter] - 1];
  50.     }
  51.  
  52.     printf("\n");
  53.   }
  54.  
  55.   return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top