題解:P1441 砝碼稱重

思路：

1.搜尋參數：目前已經選取的個數;已經放棄的個數

2.搜尋剪枝：放棄的比m多，則return

3.搜尋邊界：如果已選取了n個：如果正好放棄了m個，dp；return

3.搜尋内容：(1)不放棄目前砝碼

　　　　　　(2)放棄目前砝碼

4.标記：是否被放棄

5.DP：利用背包解決

代碼：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 2010;

int n, m, ans;
int a[MAXN], vis[MAXN], f[MAXN];

void dp()
{
    memset(f, 0, sizeof(f));
    f[0] = 1;
    int ret = 0, sum = 0;
    for(int i=0; i<=n; i++)
    {
        if(vis[i])
            continue;
        for(int j=sum; j>=0; j--)
        {
            if(f[j] && !f[j + a[i]])
            {
                f[j + a[i]] = 1;
                ret ++;
            }
        }
        sum += a[i];
    }
    ans = max(ans, ret);
}

void dfs(int get, int give_up)
{
    if(give_up > m)
    {
        return ;
    }
    if(get == n)
    {
        if(give_up == m)
        {
            dp();
        }
        return ;
    }
    dfs(get + 1, give_up);
    vis[get] = 1;
    dfs(get + 1, give_up + 1);
    vis[get] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        cin >> a[i];
    }
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}      

轉載于:https://www.cnblogs.com/LonelyFish/p/10629934.html