题干：N 个物品，每个物品有对应的价值和体积，背包容量为 V，如何选择物品使得在不超过背包容量的前提下，价值之和最大。 每个物品都可以选和不选，两种选择，那么一共有 $2^N$ 两种方案，所以题目是一个有限集合的最值问题，所以可以用 y 氏 DP 法来分析

步骤一：状态表示

$f(i,j)$

  • 确定集合：（i 和 j 表示的意思）在只考虑前 i 个物品，并且物品总体积不超过 j 的选法的集合
  • 属性：（$f(i,j)$ 的值代表的意思，和题意相关）当前集合中的最大价值
  • image.png

步骤二：状态计算

  • 那么 $f(i,j)$ 如何计算呢，对于上述的集合，我们可以分为两个子集
    • 一个子集是没有选择物品 i 的集合
      • 如果不选择物品 i，那么我们只需要找到只考虑前 $i-1$ 个物品，并且物品总体积不超过 j 的选法集合中的最大价值，也就是 $f(i-1,j)$
    • 一个子集是选择了物品 i 的集合
      • 如果选择了物品 i，那么我们只需要找到只考虑前 $i-1$ 个物品，并且物品总体积不超过 $j-v[i]$ 的选法集合中的最大价值，也就是 $f(i-1,j-v[i])$
      • 然后加上物品 i 的价值 $w [i]$ $f(i-1,j-v[i])+w[i]$
      • 注意 j 和 v[i]的大小

板子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;

int n,v;
int V[N],W[N];
int dp[N][N];

int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>V[i]>>W[i];
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=v;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=V[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-V[i]]+W[i]);
        }
    }
    cout<<dp[n][v];
    return 0;
}

优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
int n,v;
int V[N],W[N];
int dp[N];
int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>V[i]>>W[i];
    for(int i=1;i<=n;i++)
        for(int j=v;j>=V[i];j--)
            dp[j]=max(dp[j],dp[j-V[i]]+W[i]);
    cout<<dp[v];
    return 0;
}