经典的0/1背包问题,使用递推公式。从最后一个物件拿还是不拿开始往前推。一开始看0/1背包的知识点是说用二维数组。这样是直观一点,初学好理解。但是后面看还可以空间优化,使用一维数组更好。

递推公式:dp[i][j]=j<w[i]?dp[i-1][j]:max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);

dp[i][j]代表拿(这里用拿还不妥当,用“考虑”比较好,因为我把每件物品都看了但是不一定拿了 。)了第i件物品承重最大为j的时候的总价值,w[i]代表重量, v[i]代表价值。dp[i-1][j]代表不拿当前物品, dp[i-1][j-w[i]]+v[i]代表拿了当前物品,取它们中最大的就好(如果这里想不清可以想想如果当前物品非常重会是什么样的情况,个人难点,仅供参考)。关于背包问题更加详细的解释可以参考(fly1988happy的博客园),有图就是好理解。


题目:飞机票直达(M - 基础DP


代码:

二维数组版本:

Memory: 5652 KB
Time: 62 MS
Language: C++
Result: Accepted


#include <iostream>
#include <algorithm>
#include <memory.h>
#include <cstdio>
using namespace std;
const int maxn=1000+1;
int v[maxn], w[maxn], dp[maxn][maxn], n, m;
void Init()
{
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));
    memset(dp, 0, sizeof(dp));
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)scanf("%d", &v[i]);
    for(int i=1;i<=n;i++)scanf("%d", &w[i]);
}
int main()
{
    int x;
    scanf("%d", &x);
    while(x--)
    {
        Init();
        for(int i=1;i<=n;i++)
            for(int j=m;j>=0;j--)
            dp[i][j]=j<w[i]?dp[i-1][j]:max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
        printf("%d\n", dp[n][m]);
    }
    return 0;
}


以一维数组优化版:

Memory: 1736 KB
Time: 31 MS
Language: C++
Result: Accepted
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <cstdio>
using namespace std;
const int maxn=1000+1;
int v[maxn], w[maxn], dp[maxn], n, m;
void Init()
{
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));
    memset(dp, 0, sizeof(dp));
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)scanf("%d", &v[i]);
    for(int i=1;i<=n;i++)scanf("%d", &w[i]);
}
int main()
{
    int x;
    scanf("%d", &x);
    while(x--)
    {
        Init();
        for(int i=1;i<=n;i++)
            for(int j=m;j>=0;j--)
                dp[j]=j>=w[i]?max(dp[j], dp[j-w[i]]+v[i]):dp[j];
        printf("%d\n", dp[m]);
    }
    return 0;
}