题目描述

blablabla

样例

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20;
int c[N], sum[N];
int rt = N;
int n, w;

void dfs(int u, int k){
    if(k > rt) return;
    if(u == n){
        rt = min(rt, k);
        return;
    }
    for(int i = 0; i < k; i++){
        if(sum[i] + c[u] <= w){
            sum[i] += c[u];
            dfs(u+1, k);
            sum[i] -= c[u];
        }
    }
    sum[k] = c[u];
    dfs(u+1, k+1);
    sum[k] = 0;
}

int main(){
    cin >> n >> w;
    for(int i= 0; i < n; i++){
        cin >> c[i];
    }
    sort(c, c+N);
    reverse(c, c+N);
    dfs(0,0);
    cout << rt << endl;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla