总时间限制: 1000ms 内存限制: 65536kB

描述

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm i_in the supplied list has a weight _W(1 ≤ W≤ 400), a ‘desirability’ factor D(1 ≤ D≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

输入

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: W and D

输出

Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

样例输入

4 6
1 4
2 6
3 12
2 7

样例输出

23

思路

设F[i][j]表示前 i 种物品, 使它们总重量不超过 j 的最优取法取得的价值总和.
题目要求F[N][M].

边界条件

if( w[1] <= j )
    F[1][j] = d[1];
else
    F[1][j] = 0;

如果第1种物品的重量小于j, 我们就把它塞进背包, 价值总和为d[1].

否则, 我们不拿第1种物品.

递推公式

F[i][j] = max( F[i-1][j], F[i-1][ j-w[i] ]+d[i] );

到了第i种物品, 我们可以要它也可以不要它.

• 如果不要第 i 种物品, 我们则要在第 i-1 种物品里凑出重量不超过 j 的拿法.
• 如果要第 i 种物品, 我们则在第 i-1 种物品里凑出重量为 j-w[i] 的拿法, 再加上第 i 种物品的价值d[i].

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[30000];
int N, M;
typedef struct Bracelet {
    int weight;
    int desirability;
}Bracelet;
int main() {
    /* Read data and initialize */
    cin >> N >> M;
    Bracelet* obj = new Bracelet[M+4];
    for(int i = 1; i <= N; i++) {
        cin >> obj[i].weight >> obj[i].desirability;
    }
    memset(dp, 0x0, sizeof(dp));
    /* Compute function */
    for(int i = 1; i <= N; i++) {
        for(int j = M; j >= obj[i].weight; j--) {
            dp[j] = max( dp[j], 
                    dp[j-obj[i].weight] + obj[i].desirability );
        }
    }
    /* Display result */
    cout << dp[M] << endl;
    delete[] obj;
    return 0;
}