01背包

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。

问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

更具体的，抽象问题为：

有n个可选项，价值为vi，耗费wi，在总耗费为C的情况下选取，求总价值最大

使用dp[i][j]表示面对第i个可选项，耗费为j时所能取到的最大值，面临的只有两种选择，取当前项，或者不取当前项：
$$dp[i][j]=\{\begin{array}{ll}dp[i-1][j],& \text{j}<wi\\ max(dp[i][j-wi]+vi,dp[i-1][j])& \text{j}>=wi\end{array}$$
自底向上遍历，先遍历物品，再遍历耗费，相当于先记录下来了底层物品，低容量的记录，顶层知道记录，因此可以快速做出判断。

    for(int i=1;i<=n;i++){for(int j=1;j<=c;j++){if(j>=w[i])m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);elsem[i][j]=m[i-1][j];}}

需要注意的是，任何动归实现时都要注意边界条件与底层条件的设置，一定要符合公式的语义

确定能获取最大价值的选择项

另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样，则x[n]=0 ; 否则 x[n]=1。当x[n]=0时，由m[n-1][c]继续构造最优解；当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，这种方式只能获取一个最优解。

    for(int i=n;i>1;i--){if(m[i][c]==m[i-1][c])x[i]=0;else{x[i]=1;c-=w[i];//向下寻找}}x[1]=(m[1][c]>0)?1:0;//只剩下最后一个了，判断是否能拿即可