动态规划 01背包 POJ-3624 Charm Bracelet

题目链接：[ POJ - 3624 ]

题目大意

0-1背包

思路

用 F[i][j] 表示取前i种物品，使它们总体积不超过j的 最优取法取得的价值总和。要求 F[N][M] 边界:

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

用 F[i][j] 表示取前i种物品，使它们总体积不超过j的 最优取法取得的价值总和
递推: F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])
取或不取第 i种物品，两者选优 ( j-w[i] >= 0 才有第二项)

F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])
本题如用记忆型递归，需要一个很大的二维数组，会超内存。注意到这个二维数组的下一行的值，只用到了上一行的正上方及左边的值，因此可用滚动数组的思想，只要一行即可。即可以用一维数组，用“人人为我” 递推型动归实现。

题解代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 4000;
int dp[13000];
int a[maxn], b[maxn];

int main(void)
{
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &a[i], &b[i]);

        for (int i = 1; i <= n; i++)
            for (int j = m; j >= a[i]; j--)
                dp[j] = max(dp[j], dp[j-a[i]] + b[i]);

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

    return 0;
}