01背包

题目大意

有$N$件物品和一个容量为$V$的背包。第$i$件物品的费用是$w[i]$，价值是$v[i]$v，求背包能装下物品的最大价值。

基本思路

01背包的特点是每种物品只有一件，只能选择放或者不放
状态可划分为用$dp[i][j]$代表将前$i$件物品放入容量为$j$的背包时可获得的最大价值，状态转移方程为
$$dp[i][j] = max(dp[i-1][j],dp[i-1][ j-w[i] ]+v[i])$$
考虑第i件物品放或者不放的情况，若不放则与只考虑前$i-1$件物品为同一个问题,若放则价值为背包容量为$j-w[i]$时的最大价值再加上物品$i$的价值$v[i]$，两种情况的最大值即为$dp[i][j]$的值。

优化方案

  1. dp数组的每一行都由上一行的前几列得出，与其他行无关，所以可用滚动数组将空间复杂度优化至$O(2n)$
  2. 从列上考虑dp数组每一列之与前面的列有关，所以可以从后往前遍历dp数组的每一行，这样在得到后面项答案的同时不会对前面的项产生影响，将空间复杂度优化至$O(n)$
    $$dp[j]=max(dp[j],dp[j-w[i]]+v[i])$$

不总结了，这篇写的足够好了：https://blog.csdn.net/yandaoqiusheng/article/details/84782655