洛谷题单指南-状态压缩动态规划-P1441 砝码称重

原题链接：https://www.luogu.com.cn/problem/P1441

题意解读：n个砝码去掉m个能称出的重量数。

解题思路：

1、暴力法

用二进制整数1~2^n - 1表示选取砝码的状态，取0的个数是m的状态表示去掉m个，然后针对剩下的砝码通过dfs枚举出所有可能的重量，每种状态求得的重量数取max。

时间复杂度：最大C(20,4) 2^16 ≈ 310^8，显然无法通过。

60分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25, M = 2005;

int a[N]; 
set<int> s;
int n, m, ans;

//计算二进制中0的个数
int count(int x)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
        if(!(x >> i & 1))
            cnt++;
    return cnt;
}

void dfs(int k, int sum, int state)
{
    if(sum) s.insert(sum);
    if(k == n) return;
    dfs(k + 1, sum, state); 
    if(state >> k & 1) dfs(k + 1, sum + a[k], state); 
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 1; i < 1 << n; i++)
    {
        if(count(i) == m)
        {
            s.clear();
            dfs(0, 0, i);
            ans = max(ans, (int)s.size());
        }
    }
    cout << ans;
    return 0;
}

2、优化暴搜

问题的关键在于如何求给定数量的砝码能称出的重量数。

砝码数量最多20，每个砝码重量最大100，也就是能称出的最大重量不超过2000，那么可以考虑枚举所有砝码，根据前i个砝码能否称出重量j，枚举重量j，实现状态的转移。

设f[i][j]=1表示前i个砝码能称出重量j，

如果不选第i个砝码，有f[i][j] = f[i - 1][j]；如果选第i个砝码，有f[i][j] = f[i - 1][j - a[i]]。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25, M = 2005;

int a[N];
bool f[N][M]; //f[i][j]=1表示前i个砝码能称出重量j
int n, m, ans;

//计算二进制中0的个数
int count(int x)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
        if(!(x >> i & 1))
            cnt++;
    return cnt;
}

int dp(int stat)
{
    int res = 0;
    memset(f, 0, sizeof(f));
    for(int i = 0; i <= n; i++)
        f[i][0] = true;
    for(int i = 1; i <= n; i++) //枚举所有砝码
    {
        for(int j = 0; j <= 2000; j++) //枚举所有当前砝码可称出的重量
        {
            f[i][j] = f[i - 1][j];
            if((stat >> i - 1 & 1) && j - a[i] >= 0)
                f[i][j] |= f[i - 1][j - a[i]];
        }
    }
    for(int i = 1; i <= 2000; i++) res += f[n][i];
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < 1 << n; i++)
    {
        if(count(i) == m)
        {

            ans = max(ans, dp(i));
        }
    }
    cout << ans;
    return 0;
}

进一步优化为一维，f[i]表示能否称出重量i

注意重量的枚举要改成从大到小，状态的转移要增加判断条件

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 25, M = 2005;

int a[N];
bool f[M]; //f[i]=1表示能称出重量i
int n, m, ans;

//计算二进制中0的个数
int count(int x)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
        if(!(x >> i & 1))
            cnt++;
    return cnt;
}

int dp(int stat)
{
    int res = 0;
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for(int i = 1; i <= n; i++) //枚举所有砝码
    {
        for(int j = 2000; j >= 0; j--) //枚举所有当前砝码可称出的重量
        {
            if((stat >> i - 1 & 1) && j - a[i] >= 0 && f[j - a[i]])
                f[j] = f[j - a[i]];
        }
    }
    for(int i = 1; i <= 2000; i++) res += f[i];
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < 1 << n; i++)
    {
        if(count(i) == m)
        {

            ans = max(ans, dp(i));
        }
    }
    cout << ans;
    return 0;
}