963 AlvinZH打怪刷经验

思路

这不是一道普通的01背包题。大家仔细观察数据的范围，可以发现如果按常理来的话，背包容量特别大，你也会TLE。

方法一：考虑01背包的一个常数优化----作用甚微。考虑到V很大时，由于只需要dp[V]的值，倒推前一个物品，只要知道dp[V-Wn]即可。以此类推，对以第j个背包，其实只需要知道到dp[V-sum{w[j..n]}]即可。这是DP无后效性的理解。

什么是01背包常数优化？

这种方法可以卡着时间点过这题，具体参考参考代码一。

方法二：动态规划需要变通！！！发现价值之和的最大值只有10^5，逆向思维，容量与价值概念互换，用最大价值来求最小容量；即，把价值之和看作是背包容量，转化为求最大价值对应的最小容量进行背包。

效率很高，不是上一种方法能比的，毕竟差了好几个数量级。具体参考参考代码二。

参考代码一

//

// Created by AlvinZH on 2017/11/16.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <cstdio>

#include <iostream>

#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, sum;

int Weight[102];//体积

int Value[102];//价值

int dp[100005];

int main()

{

    while(~scanf("%d %d", &n, &m))

    {

        int wSum = 0, vSum = 0;

        memset(dp, INF, sizeof(dp));

        for (int i = 0; i < n; ++i) {

            scanf("%d %d", &Weight[i], &Value[i]);

            wSum += Weight[i];

            vSum += Value[i];

        }

        dp[vSum] = wSum;

        for (int i = 0; i < n; ++i) {

            for (int j = Value[i]; j <= vSum; ++j) {

                if(dp[j] - Weight[i] >= 0)

                    dp[j - Value[i]] = min(dp[j-Value[i]], dp[j]-Weight[i]);

            }

        }

        for (int i = vSum; i >= 0; --i) {

            if(dp[i] <= m) {

                printf("%d\n", i);

                break;

            }

        }

    }

}

参考代码二

//

// Created by AlvinZH on 2017/11/16.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <cstdio>

#include <iostream>

#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, sum;

int Weight[102];//体积

int Value[102];//价值

int dp[100005];

int main()

{

    while(~scanf("%d %d", &n, &m))

    {

        int wSum = 0, vSum = 0;

        memset(dp, INF, sizeof(dp));

        for (int i = 0; i < n; ++i) {

            scanf("%d %d", &Weight[i], &Value[i]);

            wSum += Weight[i];

            vSum += Value[i];

        }

        dp[0] = 0;

        dp[vSum] = wSum;

        for (int i = 0; i < n; ++i) {

            for (int j = vSum; j >= Value[i]; --j) {

                if(dp[j] > dp[j-Value[i]] + Weight[i])

                    dp[j] = dp[j-Value[i]] + Weight[i];

            }

        }

        for (int i = vSum; i >= 0; --i) {

            if(dp[i] <= m) {

                printf("%d\n", i);

                break;

            }

        }

    }

}