01背包


/**
 *  背包问题:
 *      N件物品,容量为V的背包,第i件物品容量C[i]、价值W[i]
 *      求如何填充这个背包能使价值最大
 *  01背包:
 *      每件物品只有一个
 *      注:01表示每件物品可以放0个或者1个
 *  算法:
 *      时间O(NV),空间O(NV)
 *      本次不压缩空间
 *  变量说明:
 *      本次采用精确定义d[i][v],输出方案更舒服:
 *          定义:只考虑前i件物品,容量恰好用到v时,能达到的最大价值
 *          初值:d[0][0]=0, d[other]=-1(表示无意义)
 *          更新:d[i][v] <- w,表示如果d[i][v]没有值,则直接赋值;如果有,则取最大的
 *          推导:
 *              本次从d[i][v]推过去:       (要求i=0~N-1)
 *                  d[i+1][v] <- d[i][v]
 *                  d[i+1][v+C[i+1]] <- d[i][v] + W[i+1]    (要求v+C[i+1]<=V)
 *              提及向d[i][v]归过来:       (要求i=1~N)
 *                  d[i][v] <- d[i-1][v]
 *                  d[i][v] <- d[i-1][v-C[i]] + W[i]        (要求v-C[i]>=0)
 *          结果:max(d[N][0~V])
 *      顺带介绍模糊定义d[i][v],不输出方案时的可用于偷懒:
 *          定义:只考虑前i件物品,容量最多用到v时,能达到的最大价值
 *          初值:d[0][0~V]=0, d[other]=-1(表示无意义)
 *          更新:d[i][v] <- w,表示如果d[i][v]没有值,则直接赋值;如果有,则取最大的
 *          推导:
 *              从d[i][v]推过去:       (要求i=0~N-1)
 *                  d[i+1][v] <- d[i][v]
 *                  d[i+1][v] <- d[i+1][v-1]                (要求v-1>=0)
 *                  d[i+1][v+C[i+1]] <- d[i][v] + W[i+1]    (要求v+C[i+1]<=V)
 *              向d[i][v]归过来:       (要求i=1~N)
 *                  d[i][v] <- d[i-1][v]
 *                  d[i][v] <- d[i][v-1]                    (要求v-1>=0)
 *                  d[i][v] <- d[i-1][v-C[i]] + W[i]        (要求v-C[i]>=0)
 *          结果:d[N][V]
 *  形象理解:
 *      把状态空间画出来就好了
 */

// TODO: 初值中后半部分的定义是冗余的

#define maxn 100
#define maxv 1000000
#define UNDEFINED -1
#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int N, V;
int C[maxn+1], W[maxn+1];
int d[maxn+1][maxv+1];

void Input() {
    FILE *in;
    int i;
    in = fopen("0.in", "r");
    fscanf(in, "%d%d", &N, &V);
    for(i=1; i<=N; ++i) {
        fscanf(in, "%d%d", &C[i], &W[i]);
    }
}

void Init() {
    int i, j;
    for(i=0; i<=N; ++i) {
        for(j=0; j<=V; ++j) {
            d[i][j] = UNDEFINED;
        }
    }
    d[0][0] = 0;
}

void update(int* site, int w) {
    if((*site) == UNDEFINED) {
        (*site) = w;
    } else {
        (*site) = max((*site), w);
    }
}

void Work() {
    int i, v;
    for(i=0; i<=N-1; ++i) {
        for(v=0; v<=V; ++v) {
            update(&d[i+1][v], d[i][v]);
            if(v+C[i+1] <= V) {
                update(&d[i+1][v+C[i+1]], d[i][v] + W[i+1]);
            }
        }
    }
}

void Output() {
    int v;
    int result = 0;
    for(v=0; v<=V; ++v) {
        result = max(result, d[N][v]);
    }
    printf("%d", result);
}

int main() {
    Input();
    Init();
    Work();
    Output();
    return 0;
}