01背包
题目
有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]，求将哪些物品装入背包可使价值总和最大。
基本思路
主要特征：每个物品只有一件，只有放与不放两种状态，设dp[i][j]表示重量限制为j时在前i个物品中能得到的最大价值
\[dp[i][j] = max(dp[i-1][j],dp[i-1][j -w[i]] + v[i])\]
因为每个物品只有两种选择则第i个不选，最大价值为dp[i-1][j],第i个要选时就要为第i个物品腾出w[i]的空间，再加上v[i];
可以发现前i个的状态都是由前i-1个推来，则可以用滚动数组滚动一维
一维情况第二层倒序枚举原因：因为是一维，正序枚举会把第i层更新的值覆盖上去，而之后又傻乎乎把被覆盖的值当做第i-1的值使用（其实也就是第i个物品可能被多次选用，完全背包将要用到）
inline void _01beibao()
{
for(rint i=1;i<=n;i++)
for(rint j=m;j>=wi[i];j--)
dp[j]=max(dp[j],dp[j-wi[i]]+vi[i]);
}求01背包第k大
inline void _01kth()
{
for(rint i=1;i<=n;i++)
{
for(rint j=m;j>=wi[i];j--)
{
int c1=1,c2=1,cnt=0;
while(cnt<=k)
{
if(dp[j][c1]>dp[j-wi[i]][c2]+vi[i]) gg[++cnt]=dp[j][c1++];
else gg[++cnt]=dp[j-wi[i]][c2++]+vi[i];
}
for(rint cc=1;cc<=k;cc++) dp[j][cc]=gg[cc];
//这里dp[j][k],表示第i层价值为j时的前k大值，显然dp[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
//然后原方程就可以解释为：dp[i][v]这个有序队列是由dp[i-1][v]和dp[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。
}
}
}完全背包
题目
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
基本特点：每个物品有无数件，状态是取0-V/w[i]件。dp[i][j]定义同上，有
\[dp[i][j] = max(dp[i][j],dp[i-1][j-k \times w[i]] + k \times v[i])\]
由于可以多次选取，正序枚举可以利用之前被w[i]更新的dp值(本质就是多次选择),也因此可滚动一维。
inline void wanquanbeibao()
{
for(rint i=1;i<=n;i++)
for(rint j=wi[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-wi[i]]+vi[i]);
}