01背包问题

基本要求：由一个最大容量为V的背包，由n个不同价值的物品，给出装入背包的最大价值

• $v[ \ \ \ ]$记录体积，$w[ \ \ \ ]$ 记录价值，$dp[ \ \ \ ][ \ \ \ ]$ 记录状态

• $\textbf{\textcolor{green}{状态计算}}$: 将 $dp[\ \ \ ][\ \ \ ]$ 分为包含第 $i$ 个数和不包含第 $i$ 个数。

有：$dp[i-1][j]\&dp[i-1][j-v[i]]+w[i]$

• 主要优化：滚动数组

优化的基础：朴素做法只用到 $dp[i]$ 和 $dp[i-1]$ 两个数组，故可以通过一个一维数组逆序更新组内数值即可。

逆序原因：01背包问题需要保证数据来源于不包含第i个物品（即前 $i-1$ 个物品的数据）。如果正序遍历，则将污染一维数组导致小下标（记为 $j$ ）的数据记录了前i个物品、容量小于 $j$ 状态下的最优解，这会导致大下标（如j+10）的数据若在此情况下再一次利用这个物品会产生 $\textbf{一物多用}$ 的情况。而逆序遍历时，由于大下标（记为K）的数据更新只依赖小下标（如K-10），所以可以保证每次更新时：1. $dp[K]$ 利用的数据是干净的 2.前K-1个状态（或者说数据）也不会被污染。

#include<iostream>
#include<algorithm>
using namespace std;

const int N =1010;

int v[N],w[N];
int dp[N][N];

int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=V;j>=0;j--)
          dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[n][V];
    return 0;
}