AWC0003 E - 荷物の配送トラック
Difficulty:None
問題文
#AWC0003 #AWC
#DFS
問題
N個の荷物と、M個のトラックがある。
荷物には重さが、トラックには積載重量が定まっている。
荷物を適当に割り当てて、N個の荷物をトラックに積むことはできるか。
解法
$ N \leq 15、$ M\leq 15なので、$ O(N^M)は間に合わない。
単純な全探索は間に合わないが、「積載重量がギリギリになるようなトラックに積む」という枝刈り？を行うことで、なんか間に合う。
実装
提出コード
code:cpp
bool solve(){
LL(n,m);
vector<ll>w(n);
cin >> w;
multiset<ll>ms;
rep(i,m){
LL(x);
ms.insert(x);
}
sort(rALL(w));
bool ok = false;
[DFS(&(auto&&f, ll pos)->void{
if(pos == n){
ok = true;
return;
}
auto it = ms.lower_bound(wpos);
rep(i,2){
if(it == ms.end()){
return;
}
ll val = *it;
if(*it - wpos>=0){
ms.insert(val - wpos);
ms.erase(ms.find(val));
f(f,pos+1);
ms.insert(val);
ms.erase(ms.find(val-wpos));
}
it = ms.lower_bound(val+1);
}
})]{DFS(DFS,0);}();
YesNo(ok);
return false;
}