1 solutions

  • 0
    @ 2021-12-4 11:57:45

    这是一个暴力可以做的题,首先遇到的物体假如能放进背包就必会被放进背包,所以从头暴力也不用排序,maxn和maxv记录本次循环的最终结果,只要背包还能放就继续放,ans和sum记录目前最大可放物体数和其体积,记得判断可放物体数相等而输出体积更大值的情况

    #include <bits/stdc++.h>
    using namespace std;
    int a[1005],V,n,ans=0,maxn,sum=0,maxv;
    int main()
    {
        cin>>V>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            maxn=0,maxv=0;
            for(int j=i;j<=n;j++)
            {
                if(maxv+a[j]<=V)
                {   
                    maxv+=a[j];
                    maxn++;
                }
            }
            if(maxn>ans)
            {
            	ans=maxn;
            	sum=maxv;
    		}
    		if(maxn==ans)
    		{
    			sum=max(maxv,sum);
    		}
        }
        cout<<ans<<" "<<sum<<endl;
        return 0;
    }
    

    Information

    ID
    199
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    109
    Accepted
    21
    Uploaded By