[数据结构与算法]01背包（动态规划）详解

最优子结构性质：大问题的最优解可以由小问题的最优解推出
无后效性：一旦f(n)确定，如何凑出f(n)就再也用不着了

如何判断一个问题能否使用DP解决：
能将大问题拆成小问题，且满足无后效性、最优子结构性质

DP为什么这么快：
暴力解法是枚举所有的可能解，这是最大的可能解空间
DP枚举有希望成为答案的解，这个空间比暴力小得多，即DP自带剪枝
其核心思想就是尽量缩小解空间

DP操作过程：（有记忆的递归）
将一个大问题转化成几个小问题
求解小问题
推出大问题的解

讨论状态转移方程：
dp[i][j]表示考虑前i个物品在容重为j的情况下的最大价值，考虑了第i个背包后，可以放入第i个背包的前提为j>weight[i],dp[i][j]的值只可从是否放入了第i个物品这两种情况推来，因为是dp[i][j]是求最大价值，所以取两种情况中的最大值,若不能放入第i个物品，则其结果和第一种情况一样dp[i][j]=dp[i-1][j]

第一种情况：
不放入第i个物品情况下的最大价值，即dp[i-1][j]，因为已经确定不放入第i个物品，所以和只考虑前i-1个物品所得的最大值(最优子问题结构）一样

第二种情况：
放入第i个物品情况下的最大值，由于已经确定放入第i个物品了，则此时的最大价值为，只考虑i-1个物品和容重为j-weight[i]情况下的最大值(最优子问题结构）+value[i]

#include <iostream>
using namespace std;
const int MAXN=1000+10;
int dp[MAXN][MAXN];
int weight[MAXN];
int value[MAXN];
int main() {
    int n,m;
    cin>>m>>n;    					//重量为m,物品个数为n
    for(int i=1;i<=n;++i)          //输入每个物品的重量和价值
        scanf("%d%d",&weight[i],&value[i]);
    for(int i=0;i<=n;++i)         //设置dp数组边界条件
        dp[i][0]=0;
    for(int j=0;j<=m;++j)
        dp[0][j]=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(j<weight[i]) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

测试用例：
input:
90 4
20 25
30 20
40 50
10 18

output:
95
由于dp[i]数组只和dp[i-1]有关，可做空间上优化，转换成一维数组

#include <iostream>
using namespace std;
const int MAXN=1000+10;
int dp[MAXN];
int weight[MAXN];
int value[MAXN];
int main() {
    int n,m;
    cin>>m>>n;    //重量为m,物品个数为n
    for(int i=1;i<=n;++i)          //输入每个物品的重量和价值
        scanf("%d%d",&weight[i],&value[i]);
    //设置dp数组边界条件 
    for(int j=0;j<=m;++j)
        dp[j]=0;
    for(int i=1;i<=n;++i){
        for(int j=m;j>=weight[i];--j){           //j<weight[i]时dp[j]即为为i-1的值，不用更新
          dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    printf("%d\n",dp[m]);
    return 0;
}