前言
上一篇文章中我们学习了简单DP，今天我们来学习一种也很常见的DP——背包DP。

程序设计思路
背包DP以01背包和完全背包为基础，其他的背包DP都由这两种延伸出去，先看01背包：
01背包是最简单的背包DP，它是指有n样物品，第i样物品的价值为xi，所占用的容量为yi，你有一个容量为m的背包，要求你用这个背包装下价值最高的物品，每种物品只能装一次。这里每样物品的状态都只有装或不装。故我们可以列出状态转移方程：fi=max(fi-1,fi-1+xi（fi表示在第1到第i个物品中选容量为j的物品能获得的最多的价值）。
完全背包与01背包的区别在于它每样物品可以选无数次，但它的状态转移方程和01背包有不同。我们可以列出状态转移方程：fi=max(fi-1+k*xi)（这里的k是指购买了k件i物品，是for循环中的变量），这样做的时间复杂度为O(n3)，明显偏慢了。但是我们还有下面的优化：fi=max(fi-1,fi+xi)，因为我们在进行这次转移前就已经充分的考虑了。这个优化必须自己想清楚。

代码实现
来看一个01背包问题：

很明显，这是一道背包题。直接看代码：

#include <bits/stdc++.h>
int n,m,a[105],dp[105][1005];//n、m、a如题意，dp指上文中i

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){//分类讨论，判断能不能买
        if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
        if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
        if(j<a[i]) dp[i][j]=dp[i-1][j];
    }
    printf("%d",dp[n][m]);
    return 0;
}

DP注重的是自己的理解，而且讲解无法达到很好的效果，请自行理解源码~

结语
背包问题是DP中较为简单的一类，要想学好DP，就应该多刷题，以此总结经验。我是faryou，再见！