洛谷P2347 砝碼稱重

題目

• 貌似是某年提高組簽到題，六重迴圈零壓力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 }

畢竟是一個可行性背包大水題，愉快地A了！