POJ-3624-Charm Bracelet-简单0/1背包、动态规划、DP

简单的0/1背包问题，用动态规划即可简单求解。
以下一段话摘自Slyar.
==========================================================
Slyar:标准的01背包，动态转移方程如下。其中dp[i,j]表示的是前i个物品装入容量为j的背包里所能产生的最大价值，w[i]是第i个物品的重量，d[i]是第i个物品的价值。如果某物品超过背包容量，则该物品一定不放入背包，问题变为剩余i-1个物品装入容量为j的背包所能产生的最大价值；否则该物品装入背包，问题变为剩余i-1个物品装入容量为j-w[i]的背包所能产生的最大价值加上物品i的价值d[i]...恩，多清晰...

if (w[i]>j) 
	dp[i,j] = dp[i-1,j]
else
	dp[i,j] = max(dp[i-1,j-w[i]]+d[i],dp[i-1,j])

==========================================================

先上一个用二维数组求解的代码，这个代码比较容易理解。为了求深理解，可以在纸上自己试着计算下这个二维数组dp。

#include <iostream>
using namespace std;

const int MAX_N = 3405;
const int MAX_M = 12885;

int dp[MAX_N][MAX_M];
int w[MAX_N];
int d[MAX_N];

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int n, m;
    cin >> n >> m;

    /*从下标1开始存放*/
    for(int i = 1; i <= n; i++) {
        cin >> w[i] >> d[i];
    }

    /*注意，i==1或者j==1时，会用到dp边界下标为0的元素，由于已经初始化这些元素为0，保证了程序的正确运行*/
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(w[i] <= j)
                dp[i][j] = max(dp[i-1][j-w[i]] + d[i], dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }

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

    return 0;
}

由于OJ上memory所限，上面代码提交上去会MLE的。在纸上计算dp过程中，发觉dp设置成n行的二维数组实际上没有必要，因为在计算dp第i行时只用到dp第i-1行的数据，而且到了最后，前面n-1行都没用的。因此，完全可以用一维数组进行计算。但要注意，应从后住前计算dp，否则dp的数据会被新计算的值覆盖，导致不正确。

#include <iostream>
using namespace std;

const int MAX_N = 3405;
const int MAX_M = 12885;

int dp[MAX_M];
int w[MAX_N];
int d[MAX_N];

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        cin >> w[i] >> d[i];
    }

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

    cout << dp[m] << endl;

    return 0;
}

观察二重for循环，可以发觉其实还可以继续进一步优化下。最终的程序版本为：

#include <iostream>
using namespace std;

const int MAX_N = 3405;
const int MAX_M = 12885;

int dp[MAX_M];
int w[MAX_N];
int d[MAX_N];

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        cin >> w[i] >> d[i];
    }

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

    cout << dp[m] << endl;

    return 0;
}