题目描述

将n件物品装入背包，可使这些物品的总体积不超过背包容量V ，且总价值W最大。
第i件物品的体积为 $v_i$ ，价值为 $w_i$

样例

输入

4 5
1 2
2 4
3 4
4 5

输出

8

算法：DP

根据题目所求问题，设有一个离散域实体 $f[i,j]$ 表示从前 $i$ 件物品中任意选择组合，使得这些物品的总体积不超过 $j$ 的价值最大值。

从前 $i$ 件物品中任意选择组合，使得这些物品的总体积不超过 $j$ ，可由两种途径得到：

1. 第 $i$ 件物品不选，此时价值最大值 $f[i,j]$ 就是 从前 $i-1$ 件物品中任意选择组合，使得这些物品的总体积不超过 $j$ 的价值最大值；即 $f[i-1,j]$；
2. 第 $i$ 件物品选，此时价值最大值 $f[i,j]$ 来自 从前 $i-1$ 件物品中任意选择组合加上 $i$ 的情况，因为加上 $i$ 之后总体积不超过 $j$，那么对应的状态应该是 从前 $i-1$ 件物品中任意选择组合，总体积不超过 $j-v_i$的价值最大值；转移状态之后价值的最大值就是它加上 $w_i$，即 $f[i-1,j-v_i]+w_i$

综上，$f[i,j]$ 由下式计算得出：

$$f[i,j] = max(f[i-1,j], f[i-1,j-v_i]+w_i)$$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 10010;
int v[N], w[N];
int f[N][N];

int n, vol;

int main(){
    cin>>n>>vol;

    for(int i = 1; i<=n; i++)cin>>v[i]>>w[i];

    for(int i = 1; i<=n ; i++)
        for(int j = 0; j<=vol; j++){
            //如果剩余空间不够，则采用不选的转移
            if(j<v[i])
                f[i][j] = f[i-1][j];
            //如果剩余空间够，则采用选与不选两种转移的较大者
            else
                f[i][j] = max(f[i-1][j] , f[i-1][j-v[i]] + w[i]);
        }
    cout<<f[n][vol];
    return 0;
}