题目

#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
int cnt[maxn];
bool ok[1 << maxn];//ok[i]表示以状态i装物品，一个背包能不能装下
int f[1 << maxn];//f[i]表示以状态i（二进制数，0表示不装，1表示装）装物品，最少要几个背包
int main(){int n, w, i, j;cin >> n >> w;for(i = 1; i <= n; i++){int x;cin >> x;x--;//x要减一！！！！因为二进制数是从第0位开始，第0位对应第0件物品cnt[x]++;}for(i = 0; i < (1 << 13); i++){int sum = 0;for(j = 0; j < 13; j++){if(i >> j & 1) sum += cnt[j];}ok[i] = (sum <= w);}f[0] = 0;for(i = 1; i < (1 << 13); i++){f[i] = 1e9;for(j = i; j; j = (j - 1) & i){//保证j中为1的位，i也为1if(!ok[j]) continue;f[i] = min(f[i], f[i ^ j] + 1);}}cout << f[(1 << 13) - 1];return 0;
}