题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

基本dp

$O(n*m)$

• 状态表示：f[i][j]表示在前i将物品中选择，并且总体积不超过j的物品的最大价值

• 状态转移：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

• 集合划分：
  1.不包含第i件物品，此时背包的最大价值就是前i-1件物品，总体积为j的最大价值
  2.包含第i件物品，此时背包的最大价值就是选择前i-1件物品,总体积为j-v[i]的最大价值

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;

int f[N][N];
int v[N],w[N];



int main(){

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

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


    printf("%d",f[n][m]);

    return 0;
}

滚动数组

$O(mn)$

y总语录：dp优化都是对代码做一个等价变形，是很简单的。（虽然我觉得很难😂）

由上面代码可以看出，代码中只使用了f[N][N]的两行，所以只开辟f[2][N]就可以了。

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;

int f[2][N];
int v[N],w[N];



int main(){

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[cnt][j]=f[(cnt+1)%2][j];
            if(j>=v[i]) f[cnt][j]=max(f[cnt][j],f[(cnt+1)%2][j-v[i]]+w[i]);

        }
        cnt=(cnt+1)%2;
    }


    printf("%d",f[(cnt+1)%2][m]);

    return 0;
}

最终算法

$O(mn)$

我们发现，虽然每一次的计算都出现了i-1和i两行，但是由于我们先计算了第i-1行，再计算了第i行，所以我们可以使用1个数组进行存储；
又因为每次计算第i行时，都需要前1行的j-v[i],所以j从后向前遍历。

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;

int f[N];
int v[N],w[N];



int main(){

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);

        }
    }


    printf("%d",f[m]);

    return 0;
}