首页 > > 程序设计 > C/C++ >

洛谷P2347 砝码称重

2018-09-18 06:25:27来源：博客园阅读 ()

题目

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

多重背包

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

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 bool dp[10005];
 6 
 7 int a,weight[7]={0,1,2,3,5,10,20},tot,v[10005],ans; 
 8 
 9 inline int read(void){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){
12         if(ch=='-') f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9'){
16         x=(x<<1)+(x<<3)+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 
22 void cf(int x,int y){
23     for(register int i=1;x-i>=0;i<<=1)
24         v[++tot]=weight[y]*i,x-=i;
25     if(x) v[++tot]=weight[y]*x;
26 }
27 
28 int main(){
29     for(register int i=1;i<=6;i++)
30         a=read(),cf(a,i);
31     dp[0]=1;
32     for(register int i=1;i<=tot;i++)
33         for(register int j=10000-v[i];j>=0;j--)
34             dp[j+v[i]]|=dp[j];
35     for(register int i=1;i<=10000;i++)
36         if(dp[i]) ans++;
37     printf("Total=%d\n",ans);
38     return 0;
39 }