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

前置知识：状压DP

洛谷传送门

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

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

这个方法实在是太暴力了

Code：

#include 
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<=0;j--){
            if((i>>j)&1){
                high_bit=1< 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)\)代表当前考虑的砝码（当然，这个砝码必须包含在当前方案里），容易想出像下面这样的状态转移方程：

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

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

#include 
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<=0;j--){
            if((i>>j)&1){
                high_bit=1<>(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})\)仍然非常高，但比之前的不知道低到哪里去了，足以通过本题。

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