装货物
装货物
https://ac.nowcoder.com/acm/problem/200532
这个题就是蓝书上边的小猫爬山和假日团队赛48的A题的升级版啊...搜索+剪枝的思想
首先判断是否有一个物品的重量超过了箱子的承重，有的话就输出No，否则继续往下。
将这个题变为最少需要的箱子个数是否小于等于m个。dfs（x,sum）为第x个货物分配过程（前x-1个货物已经分配好了，用了sum个箱子），用cnt数组记录每个箱子装了多少吨，ans记录最少需要多少个箱子。
对于第x个货物有两种情况：
- 如果货物可以放在第 i 个箱子中，那么就将 cnt[i] 加上这个货物的重量并继续递归dfs（x+1，sum）
- 用一个新的箱子装这个货物，也就是令 cnt[sum+1] = wi 。然后继续递归 dfs（x+1，sum+1）
当x==n+1的时候说明到达了边界，更新答案ans并 return。为了防止超时，可以做一些操作，可以将货物按照重量由大到小排序，优先搜索重量大的货物，减少搜索次数；可以在搜索时判断当前的sum是否大于等于ans，如果是，说明答案不会更优直接return。
最后判断一下ans和m的大小，如果ans<=m输出Yes，否则输出No。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[20];
ll cnt[20];
ll ans;
ll n,m;
void dfs(ll x,ll sum)
{
if(sum>=ans) return;
if(x==n){
ans=min(ans,sum);
return;
}
for(ll i=0;i<sum;i++){
if(cnt[i]+a[x]<=m){
cnt[i]+=a[x];
dfs(x+1,sum);
cnt[i]-=a[x];
}
}
cnt[sum]=a[x];
dfs(x+1,sum+1);
cnt[sum]=0;
}
ll cmp(ll x,ll y)
{
return x>y;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--){
ll x;
cin>>n>>x>>m;
ll flag=1;
for(ll i=0;i<n;i++) {
cin>>a[i];
if(a[i]>m) flag=0;
}
if(!flag){
cout<<"No"<<endl;
continue;
}
sort(a, a+n , cmp);
ans=n;
dfs(0,1);
if(ans>x) flag=0;
if(!flag){
cout<<"No"<<endl;
continue;
}
cout<<"Yes"<<endl;
}
return 0;
}
百度公司氛围 312人发布
投递百度等公司10个岗位 >