dp

二维状态表示

先确定状态的表示，再找到状态转移方程
我们使用二维状态表示，那么就是用i来表示前i个物品，使用空间不超过j的情况的下的最大价值和
dp[i][j]我们将状态分类为两种状态，使得两种状态能够动态递进
将dp状态分为未选取第i个物品和选取了第i个物品，分成dp[i-1][j]和dp[i-1][j-v[i]]+w[i];
这样就可以使状态依次动态递进，最后推演出dp[n][m]的值也就是前n个物品(所有物品)当中使用不超过m的空间(使用不超过最大空间)的情况下可以取到的最大价值和

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int v[N];int w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            a[i][j]=a[i-1][j];
            if(j>=v[i])a[i][j]=max(a[i][j],a[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<a[n][m];
    return 0;
}

一维状态表示

我们可以看到每一轮(i轮)当中我们我们只用到了上一轮(i-1轮)当中dp[i-1][1~m]的值，所以我们干脆可以把[i]这一维删掉，删掉之后代码变成了

for(int i=1;i<=n;i++)
    { 
        for(int j=0;j<=m;j++)
        {
            a[j]=a[j];
    /*这里当然没错，可以表示a[i][j]=a[i-1][j]，因为a[j]根本还没有更新还是上一轮(i轮)的
    态
    if(j>=v[i])a[j]=max(a[j],a[j-v[i]]+w[i]);//这里就错了，因为max括号后面的这个a[j-v[i]]中的j-v[i]
    是小于j的已经在之前的小轮(j轮)当中已经更新过了，所以这里使用的不是我们想要的a[i-1][j-v[i]]而是
    a[i][j-v[i]]，指不定是什么已经计算过的值了，所以最后的答案是是错误的*/
        }
    }

我们来举一个例子来说明这种形势下的错误
使用样例

4 5
1 2
2 4
3 4
4 5

正确的二维变化流程是
i=1 dp[1][0]=0 dp[1][1]=0/2->2 dp[1][2]=0/2->2 dp[1][3]=0/2->2 dp[1][4]=0/2->2 dp[1][5]=0/2->2
i=2 dp[2][0]=0 dp[2][1]=2 dp[2][2]=2/4->4 dp[2][3]=2/2+4->6 dp[2][4]=2/2+4->6 dp[2][5]=2/2+4->6
.....................
而我们这样的一维变化流程是
i=1 dp[0]=0 dp[1]=0/0+2->2 dp[2]=0/2+2->4 dp[3]=0/4+2->6 dp[4]=0/6+2->8 dp[5]=0/8+2>10
.....................
可以看到明显不对，所以我们为了要改变这种境况来使用一维状态表示的话我们就必须得让j从大到小来枚举每一轮(i轮)这样的话，我们在使用到a[j-v[i]]时，他仍然是未更新过的值，也就是上一轮(i轮)中的值，也就可以正常的递进更新我们的i了，最后输出我们的a[m]即可

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
int v[N];int w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            a[j]=a[j];
            if(j>=v[i])a[j]=max(a[j],a[j-v[i]]+w[i]);
        }
    }
    cout<<a[m];
    return 0;
}