hihoCoder-1038-01背包

这题就是01背包的问题，它首先满足重复子问题，假如有4个物品a、b、c、d，他们的需求数目和满意度从1开始升序。
当我们选择a、d和b、c的时候我们都需要求dp[n-1][m-5]这样的一个值，所以满足重复子问题性质。
其次满足无后效性，我们无论选择a、d还是b、c，它们的满意度对于我们的结果来说是一样的，它们为什么等于5对我而言没有区别。
然后我们可以使用一维数组来存放，是因为，如果dp[i][j]依赖于dp[a][b]，那么说明i=a+1,并且j>=b。所以，当我们使用dp[a][b]来算出dp[i][j]时候，dp[a][b]就已经没用了，我么用这个空间来存放dp[i][j]就行了。
这也就是能压缩空间的原因。

#include <cstdio>
#include <cstring>
int dp[100005];
int weight[505], value[505];
int m, n;

int max(int x,int y)
{
    return x > y ? x : y;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n;i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n;i++) {
        for (int j = m; j >= weight[i];j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    printf("%d
", dp[m]);
    return 0;
}