card.cpp

#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fin stdin
#define fout stdout
#define MAX_CARD 102
#define MAX_WEIGHT 100002

int n; 
int weight; 
int card[MAX_CARD]; 
int f[MAX_WEIGHT]; 
int path[MAX_WEIGHT]; 
bool have_card[MAX_CARD]; 

int main() {
//    FILE *fin = fopen("card.in", "r"); 
//    FILE *fout = fopen("card.out", "w"); 
    int a = 0, b = 0; 
    bool multi = false; 
    fscanf(fin, "%d", &weight); 
    fscanf(fin, "%d", &n); 
    memset(f, 0, sizeof(f)); 
    memset(path, 0xFF, sizeof(path)); 
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d", &card[i]); 
    }
    f[0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = weight; j >= card[i]; j--) {
            if(f[j - card[i]]) {
                f[j] = f[j] + f[j - card[i]]; 
                if(path[j] == -1 && f[j - card[i]]) {
                    path[j] = i; 
                }
            }
        }
    }
    if(!f[weight]) {
        fprintf(fout, "0\n"); 
        return 0; 
    }
    if(f[weight] > 1) {
        fprintf(fout, "-1\n"); 
        return 0; 
    }
    a = weight; 
    while(a) {
        have_card[path[a]] = true; 
        a = a - card[path[a]]; 
    }
    for(int i = 0; i < n; i++) {
        if(!have_card[i]) {
            fprintf(fout, "%d ", i + 1); 
        }
    }
    fprintf(fout, "\n"); 
    return 0; 
}