问题描述

有n个物品，每个物品的重量为a[i]，需将所有物品分成若干组，每组总重量不超过W，求最少分组数。

解题思路

采用状态压缩动态规划（DP）。用dp[S]表示子集S的最小分组数，va[S]表示子集S的总重量。预处理va[S]后，枚举所有子集S，对每个S枚举其非空子集s，若va[s]≤W，则更新dp[S]为dp[S-s]+1的最小值。

#include <bits/stdc++.h>
using namespace std;
const int N=18;
int a[N],dp[1<<N],va[1<<N];
int main()
{
    int n,W;cin>>n>>W;
    for(int i=0;i<n;i++)cin>>a[i];
 
    // 计算每个子集的总重量
    for(int S=0;S<(1<<n);S++)
        for(int i=0;i<n;i++)
            if(S&(1<<i))
                va[S]+=a[i];
 
    // 初始化DP数组，dp[0]=0，其余为无穷大
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
 
    // 枚举所有非空子集S
    for(int S=1;S<(1<<n);S++)
        // 枚举S的所有非空子集s
        for(int s=S;s;s=S&(s-1))
            if(va[s]<=W)  // 若子集s重量合法
                dp[S]=min(dp[S],dp[S-s]+1);  // 更新最小分组数
             
    cout<<dp[(1<<n)-1]<<'\n';  // 输出所有物品的最小分组数
    return 0;
}