梦想剪枝法

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int pack[20], weight[20];
int n, m, res = 20, cnt, k;

bool cmp(int a, int b)
{
    return a > b;
}

void dfs(int cur)
{   
    if (++k >= 9000000 || cnt >= res) return;   //梦想剪枝
    if (cur >= n)
    {
        res = cnt;
        return;
    }
    for (int i = 1; i <= cnt; ++i)
    {
        if (pack[i] + weight[cur] <= m) 
        {
            pack[i] += weight[cur];
            dfs(cur + 1);
            pack[i] -= weight[cur];
        }
    }
    pack[++cnt] = weight[cur];
    dfs(cur + 1);
    pack[cnt--] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &weight[i]);
    dfs(0);
    printf("%d", res);
    return 0;
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int pack[20], weight[20];
int n, m, res = 20, cnt;

bool cmp(int a, int b)
{
    return a > b;
}

void dfs(int cur)
{
    if (cnt >= res) return;
    if (cur >= n)
    {
        res = cnt;
        return;
    }
    for (int i = 1; i <= cnt; ++i)
    {
        if (pack[i] + weight[cur] <= m) 
        {
            pack[i] += weight[cur];
            dfs(cur + 1);
            pack[i] -= weight[cur];
        }
    }
    pack[++cnt] = weight[cur];
    dfs(cur + 1);
    pack[cnt--] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &weight[i]);
    sort(weight, weight+n, cmp);
    dfs(0);
    printf("%d", res);
    return 0;
}