[状压DP]P1441 题解砝码称重

emm....看到题目，我第一个想到的就是枚举。暴力大法好！

具体怎么枚举？当然是子集枚举啦！枚举出每一个可能的砝码选择方案。对于每一个合法的（也就是选取数量等于\(n-m\)的）方案，求出这个方案能称出重量的数量。至于如何求重量的数量，枚举出这个方案所有的子方案，再对每个子方案的和去重。

这个方法实在是太暴力了

Code：

#include <bits/stdc++.h>

using namespace std;

#define MAXN 22

#define MAXA 2005

int n,m,a[MAXN],ans,sum[1<<22],cnt[1<<22];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%d",a+i);

    }

    for(int i=1;i<(1<<n);i++){//状压

        int high_bit=0,high_bit_num=0;

        for(int j=31;j>=0;j--){

            if((i>>j)&1){

                high_bit=1<<j;

                high_bit_num=j;

                break;

            }

        }//求出当前方案的最高位

        sum[i]=sum[i^high_bit]+a[high_bit_num+1];//转移。因为i是“按顺序”枚举的，所以去掉最高位后的方案一定枚举过了。

        cnt[i]=cnt[i^high_bit]+1;

    }

    for(int i=1;i<(1<<n);i++){

        if(cnt[i]==n-m){

            set<int> heavy;//set有自动去重的功效

            for(int j=1;j<=i;j++){

                if((j|i)==i){

                    heavy.insert(sum[j]);//枚举每个子方案

                }

            }

            ans=max(ans,int(heavy.size()));//取大

        }

    }

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

    return 0;

}

但是，虽然暴力打得很爽，时间复杂度也非常爆炸。时间复杂度达到了可怕的\(O((2^{n})^2)\)！ 所以，优化是必须的。

可以考虑对求重量的数量的过程进行优化。定义状态\(dp(i)\)代表当前方案能否称出重量\(i\)，\(a(j)\)代表当前考虑的砝码（当然，这个砝码必须包含在当前方案里），容易想出像下面这样的状态转移方程：

\[dp(i)=dp(i-a(1)) \operatorname{OR} dp(i-a(2))...\operatorname{OR} dp(i-a(n))
\]

这个方程翻译成人话的意思就是：如果一个重量可以被组合出来，那么再加一个砝码也能被组合出来。反过来就是，如果一个重量减去一个砝码的重量能被组合出来，那么这个重量能够被组合出来。

有了状态转移方程，代码就非常好写了。

#include <bits/stdc++.h>

using namespace std;

#define MAXN 22

#define MAXA 2005

int n,m,a[MAXN],cnt[1<<22],dp[MAXA],ans;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%d",a+i);

    }

    for(int i=1;i<(1<<n);i++){//状压

        int high_bit=0,high_bit_num=0;

        for(int j=31;j>=0;j--){

            if((i>>j)&1){

                high_bit=1<<j;

                high_bit_num=j;

                break;

            }

        }//求出当前方案的最高位

        cnt[i]=cnt[i^high_bit]+1;//转移。因为i是“按顺序”枚举的，所以去掉最高位后的方案一定枚举过了。

    }

    for(int i=1;i<(1<<n);i++){

        if(cnt[i]==n-m){

            fill(dp,dp+2000+1,false);

            dp[0]=true;

            for(int j=1;j<=n;j++){

                if(i>>(j-1)&1){//如果当前砝码在方案里才考虑

                    for(int k=2000;k>=a[j];k--){

                        dp[k]|=dp[k-a[j]];

                    }

                }

            }

            int cnt=0;

            for(int k=1;k<=2000;k++){

                if(dp[k]){

                    cnt++;

                }

            }

            ans=max(ans,cnt);

        }

    }

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

    return 0;

}

时间复杂度是\(O(2^n\times n \times \max{a_i})\)仍然非常高，但比之前的不知道低到哪里去了，足以通过本题。

你都看到这儿了不考虑点一个赞吗

巴特西

[状压DP]P1441 题解砝码称重

最新文章

热门文章

巴特西

[状压DP]P1441 题解 砝码称重

最新文章

热门文章

[状压DP]P1441 题解砝码称重