1 solutions
-
0
这是一个暴力可以做的题,首先遇到的物体假如能放进背包就必会被放进背包,所以从头暴力也不用排序,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; }
- 1
Information
- ID
- 199
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 109
- Accepted
- 21
- Uploaded By