POJ3624

题目：往手镯上镶嵌宝石，当然所嵌宝石的总重量是有上限的，要求所嵌宝石的总价值最大。这其实就是一个01背包问题。
链接：

思路：设M为总重量上限，一共有n颗宝石，那么开一个数组记录各个状态state[n][M+1]
        state[i][j] = max {state[i-1][j], state[i-1][j-wi]}， 其实就是选择要或者不要第二颗宝石。
时间复杂度为O(M*n)，当然空间是可以降下来的。

我一开始忘记吧第M+1个状态copy过去，就一直WA，真是脑残啊。

上代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAX 12881

int state[2][MAX];

int N, M;

int dp() {
    int w, d;
    int pre, cur;
    memset(state, 0, sizeof(state));
    for (int i=0; i<N; i++) {
        cin >> w >> d;
        pre = (i + 1) % 2;
        cur = i % 2;
        memcpy(state[cur], state[pre], sizeof(int)*(M+1));
        for (int k=1; k<=M-w; k++) {
            if (state[pre][k] > 0 &&
                    state[pre][k+w] < state[pre][k] + d) {
                state[cur][k+w] = state[pre][k] + d;
            }
        }
        if (state[cur][w] < d)
            state[cur][w] = d;
    }
    int max = 0;
    for (int k=1; k<=M; k++)
        if (max < state[cur][k])
            max = state[cur][k];

    return max;
}

int main() {
    while (cin >> N >> M)
        cout << dp() << endl;
    return 0;
}