洛谷P2347 砝码称重

题目

---

• 貌似是某年提高组签到题，六重循环零压力AC，差点怒踩std
• 但本蒟蒻决定写正解——多重背包，果断20分
• 原因是写错了状态转移方程。。。神才知道我咋过的样例和两个测试点
• 扯远了

---

多重背包

• 简单说一下多重背包
• 限制某一些物体个数的背包
• 可以参考fengzw的背包问题：0-1背包、完全背包和多重背包
• 这里只说一下二进制拆分
• 我们要保证可以选出一个物品的所有可能数量
• 若它有n个，那么从2开始，一直到⌊logn⌋中，每次以2分为一组
• 剩下的n-⌊logn⌋单独为一组即可
• 可以证明这种方法正确，在此不再赘述
• 然后就是一个愉快的01背包

---

 #include<bits/stdc++.h>

 using namespace std;

 bool dp[];

 int a,weight[]={,,,,,,},tot,v[],ans;

 inline int read(void){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){

         if(ch=='-') f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 void cf(int x,int y){

     for(register int i=;x-i>=;i<<=)

         v[++tot]=weight[y]*i,x-=i;

     if(x) v[++tot]=weight[y]*x;

 }

 int main(){

     for(register int i=;i<=;i++)

         a=read(),cf(a,i);

     dp[]=;

     for(register int i=;i<=tot;i++)

         for(register int j=-v[i];j>=;j--)

             dp[j+v[i]]|=dp[j];

     for(register int i=;i<=;i++)

         if(dp[i]) ans++;

     printf("Total=%d\n",ans);

     return ;

 }

毕竟是一个可行性背包大水题，愉快地A了！