[POI2007]ODW-Weights(贪心)

在byteotian公司搬家的时候，他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运，并且丢弃剩下的砝码。每个容器可以装的砝码数量有限制，但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个砝码都有一个特征，他们的中总有一个的重量是另外一个的整数倍，当然他们也可能相等。

Solution

关键的地方就是任意两个物品之间都是整数倍之间的关系。

我们可以吧每个容器k进制拆分，那么我们把物品从小到大依次加入，如果当前位不满足，就从高位借。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100002
using namespace std;
int a[N],b[N],c[N],tot,d[N],ji[N],n,m;
int dfs(int id){
    if(id>tot)return 0; 
    if(d[id])return d[id]--,1;
    if(dfs(id+1)){
      d[id]+=c[id+1]/c[id],d[id]--;
      return 1;
    }
    return 0; 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)scanf("%d",&b[i]); 
    sort(b+1,b+m+1); 
    for(int i=1;i<=m;++i){
        if(b[i]!=b[i-1])c[++tot]=b[i];
        ji[i]=tot;
    }
    for(int i=1;i<=n;++i)
     for(int j=tot;j>=1;--j){
         d[j]+=a[i]/c[j];a[i]%=c[j];
     }
     int now=1;
    for(int i=1;i<=m;++i){
        if(!dfs(ji[i])){
            printf("%d",i-1);
            return 0;
        }
        if(i==m)cout<<m;
    }
    return 0;
}