第一題:梱包問題(NOIP 2009試験問題12.08)

梱包の問題
【問題の説明】:1つの箱の容量はv(正の整数、o≦v≦20000)であり、同時にn個の物品(o≦n≦30)があり、各物品に1つの体積(正の整数)がある.m個の物品のうち、任意に千個を箱に入れ、箱の残りの空間を最小限に抑えることが要求される.
【例】
【入力】:(boxes.in)
24個の整数は、箱容量6個の整数を表し、n個の物品8の次のn行を表し、それぞれこのn個の物品のそれぞれの体積を表す.3 12 7 9【出力】:(boxes.out)
0ボックスの空き容量を表す整数です.

#include <stdio.h>
#include <stdlib.h>
int n, v;
int d[31];
int ans = 0;
void process(int i, int carry)
{
    if (i > n) return ;
    if (carry <= v) {
        if (carry > ans) ans = carry;
    } else return ;
    process(i + 1, carry);
    if (carry + d[i] > v) return ;
    else process(i + 1, carry + d[i]);    
}
int main()
{
    FILE *in,*out;
    ans = 0;
    in = fopen("boxes.in","rt");
    out = fopen("boxes.out","wt");
    fscanf(in, "%d", &v);
    fscanf(in, "%d", &n);
    int i, j, k;
    for (i = 0; i < n; ++i)
        fscanf(in, "%d", &d[i]);
    process(0, 0);
    fprintf(out, "%d
", v - ans);
    system("pause");
    fclose(in);
    fclose(out);
    return 0;
}
/*
24
6
8 3 12 7 9 7
*/