装箱问题

把体积当做价值

#include <iostream>

using namespace std;

int a[200010];
int f[200010];

int main()
{
    int v;
    cin>>v;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=v;j>=1;j--)
        {
            if(j>=a[i])
            f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
    }
    int res=v-f[v];

    cout<<res;


    return 0;
}

2023/11/27

没啥难度，轻松ac
01背包

#include <iostream>

using namespace std;

const int N=20020;

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

int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[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]] + v[i]);
            }
        }
    }

    cout<<m - f[n][m];
    return 0;
}