01背包

//有N件物品和一个容量为 V的背包，每件物品有各自的价值且只能被选择一次，
//要求在有限的背包容量下，装入的物品总价值最大。

//及只需要决策选与不选

//状态表示：f[i][j]，从前i给物品选，体积小于等于j
//状态计算：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]+w[i])

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1010;

int n,m;
int v[N],w[N];
int f[N][N];//表示最大值

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++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }

        cout<<f[n][m]<<endl;

        return 0;
}


//一维优化->等价变形
//f[j]就是前i轮已经决策的物品且背包容量j下的最大价值。

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1010;

int n,m;
int v[N],w[N];
int f[N];//表示最大值

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>=v[i];j--)
        {

            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

        cout<<f[m]<<endl;

        return 0;
}