自动搬运

查看原文

来自洛谷，原作者为

	XiXi 我永远喜欢东风谷早苗

搬运于2025-08-24 21:43:30，当前版本为作者最后更新于2018-01-09 14:56:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很简单的01背包，每件物品的价值和重量相同，直接套就行了。还有其中有个点要优化，在中途进行判断就好了，当然开O2优化也行

`

    #include<bits/stdc++.h>
    using namespace std;
    int f[111111];
    int main()
    {
        int n,m,i,j,a[111111];
        cin>>m>>n;
        for (i=1;i<=n;i++) scanf("%d",&a[i]);
        for (i=1;i<=n;i++)
        {
            for (j=m;j>=a[i];j--)
            f[j]=max(f[j],f[j-a[i]]+a[i]);
            if (f[m]==m) {printf("%d",m); return 0;}//优化，如果已经达到最好的结果（装满），就直接退掉
        }
        printf("%d",f[m]);
}