poj3624题解

//Memory 168K Time 157MS
#include<iostream>
#include<cstdio>

using namespace std;

int result[12900] = {0};//存储每种手镯的重量可得到的最大价值

int main() {
    int n, m;//珠宝数量,手镯最大承重量
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int w, d;//每串珠宝的重量和价值
        scanf("%d%d", &w, &d);
        //当前手镯可以承重当前珠宝
        //遍历手镯每种可能的承重量(能够承重当前珠宝)
        for (int j = m; j >= w; j--)
            //若在当前手镯的承重量下
            //装下当前遍历的珠宝可获得的价值大于之前找到的,在同样的手镯承重量下的最大价值
            //则更新当前手镯承重量可获得的最大价值
            if (result[j] < result[j - w] + d)
                result[j] = result[j - w] + d;
    }
    //打印手镯在最大承重量为m时可以获得的最大价值
    printf("%d\n", result[m]);
    return 0;
}