采药

简单01背包变种

#include <iostream>

using namespace std;

const int N=10010;

int a[N];
int w[N];
int f[N];

int main()
{
    int t,m;
    cin>>t>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>w[i];
    }

    for(int i=1;i<=m;i++)
    {
        for(int j=t;j>=1;j--)
        {

            if(j>=a[i])
            {
                f[j]=max(f[j],f[j-a[i]]+w[i]);
            }
        }
    }
    cout<<f[t];

    return 0;
}

2023/11/27

01背包
二维写法

#include <iostream>

using namespace std;

const int N=1010;

int f[N][N];
int w[N], v[N];
int n,m;

int main()
{
    cin>>m>>n;
    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];

    return 0;
}