背包问题与动态规划

1.动态规划

1.1动态规划的原理

动态规划将大问题拆分成小问题，通过寻找大问题和小问题的递推关系来，解决一个个小问题，最终达到解决原问题的效果。动态规划具有记忆性，通过填写表格把所有已经解决的子问题答案记录下来，在新问题里需要用到就可以直接提取，避免了重复使用，从而节省了时间，所以在问题满足最优性原则原理之后，用动态规划解决问题的核心在于填表，表填写完毕，最优解也就找到。

最优原则是动态规划的基础，最优性原理在于“多阶段决策过程的最优决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面的决策造成的某一状态而言，其后各阶段的决策序列必须构成最优决策”。

1.2动态规划的总体思路

根据动态规划的解题步骤：

问题抽象化
建立模型
寻找约束条件
判断是否满足最优条件
分析大问题与小问题的递推关系式
填表
寻找解的组成

2.例题之背包问题

2.1题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤1000

输入样式

输出样式

2.2问题分析

在解决问题之前，为了描述方便，首先定义一些变量: v[i]代表第i个物品的价值，w[i]代表第i个物品的体积大小。设置f(i,j): 代表在 j 当前背包的容量下，前 i 个组合下背包的最佳组合对应的价值。

根据动态规划解题步骤：

建立模型即求max(v1X1+v2X2+…+vnXn)；
寻找约束条件，w1X1+w2X2+…+wnXn<capacity；
寻找递推关系式，面对当前商品有两种可能性：
- 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的
- 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个

可以得出递推关系式：

j<w[i] f(i-1,j)
j>=w[i] f(i,j)=max{f(i-1,j) , f(i-1,j-w[i])+v[i]}

这里对这两个关系式进行分析解释：

如果第i个物品容积w[i]大于这个背包所设置的最大容积时，无法加入到背包里那么此时背包中的价值为前i-1个物品组合所创造出的价值。即 f(i-1,j)
如果加入的第i个物品容积w[i]小于这个背包所设置的最大容积时，还要判断到底是加到背包里使物品的价值最大还是不加入背包里物品的价值最大。即判断未加入时背包的价值f(i-1,j),与加入后背包的价值：f(i-1,j-w[i])+v[i]
f(i-1,j-w[i])+v[i]如何理解？因为是加入i个物品求出其最大的价值，那么已经确定要加入背包中了由小问题推出大问题的方法需要求出前i-1个物品组合的最大价值再加上v[i]即可。第i个物品加入到背包的组合的推理公式为：f(i-1,j-w[i])+v[i]

2.3代码实现

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main(){
    cin >> n >> m; 
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; 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][m] << endl;
    return 0;
}

大功告成