描述

有一个体积为$VV$的背包，$nn$个物体，每个物体的体积和价值分别为$v_{i}v\_i$和$w_{i}w\_i$，每个物品仅可用一次，问:

• 背包能装的最大价值是多少？
• 将背包装满后的最大价值是多少？

思路

• 01背包的模板题，第一问答案为$ma{x}_{i\le V}dp[i]max\_\{i\; \backslash leq\; V\}dp[i]$，第二问答案为$dp[V]dp[V]$
• 设$dp[i][j]dp[i][j]$表示使用了$ii$个物体体积为$jj$时的最大价值，01背包的转移方程为$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]+w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]+w[i])$
• 通过从后向前遍历的方法可以省略一维存储，具体实现见代码

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;
int dp[MAXN],v[MAXN],w[MAXN];
int main()
{
    int n,V;
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=V-v[i];j>=0;j--)
            if(dp[j]>=0)
                dp[j+v[i]]=max(dp[j+v[i]],dp[j]+w[i]);
    int mx=0;
    for(int i=0;i<=V;i++)
        mx=max(mx,dp[i]);
    if(dp[V]==-1) dp[V]=0;
    printf("%d\n%d\n",mx,dp[V]);
}

时间复杂度$O(Vn)O(Vn)$，空间复杂度$O(V+n)O(V+n)$