Description


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 Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 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.


Input

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

Output

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

Sample Input


4 6
1 4
2 6
3 12
2 7
Sample Output


23
​

对于每一个物品有选或者不选
若选择一个物品的结果就是dpi-1] +d[i]也就是说没选这个物品时，且它的重量是刚好能放下当前物品的最大值+当前物品的价值。
若不选择一个物品的结果就是dpi-1 也就是说是不选择此物品时的最大值。

二维DP 会MLE

#include <iostream>
using namespace std;
const int MAXN = 3402, MAXM = 12881;
int n,m, w[MAXN], d[MAXN], dp[MAXN][MAXM];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> d[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++) {
            dp[i][j] = j-w[i] < 0 ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][j-w[i]] + d[i]);
        }
    }

    cout << dp[n][m];
    return 0;
}

滚动数组优化的一维DP

可以看到dpi 只依赖dpi-1] 与dpi-1 我们可以让原本的0~m的遍历变成m->w[i]的遍历 如果不这样子的话我们正序的遍历的时候会覆盖上面的数据，但是如果我们逆序的话是先算后面的，并不会导致前面的数据被覆盖因此可以达到数据复用的过程，本质原因是dpi依赖之前的数据 如果正序的话之前的会被覆盖。

#include <iostream>
using namespace std;
const int MAXN = 3403, MAXM = 12881;
int n,m, w[MAXN], d[MAXN], dp[MAXM];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> d[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]] + d[i]);
        }
    }

    cout << dp[m] << endl;
    return 0;
}