백준19343 Bin Packing

작성일 | In

문제 링크

  • http://icpc.me/19343

사용 알고리즘

  • Bit DP

시간복잡도

  • $O(N \times 2^N)$

풀이

$N \leq 24$이므로 Bit DP를 합시다.

D(bit) = 현재 bit처럼 물건을 가져갔을 때 (사용한 가방의 개수, 마지막 가방에서 사용한 용량)의 최솟값
으로 정의해서 Bit DP를 하면 됩니다.

켜져있는 bit가 작은 것부터 하나씩 채워주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef pair<char, int> p;

int n, s, a[33]; char cnt[1 << 24];
p dp[1 << 24]; vector<int> ord;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> s; for(int i=0; i<n; i++) cin >> a[i];
    for(int i=1; i<(1<<n); i++) cnt[i] = __builtin_popcount(i);
    ord.resize(1 << n); iota(all(ord), 0);
    sort(all(ord), [&](int a, int b){ return cnt[a] < cnt[b]; });
    for(int i=1; i<(1<<n); i++) dp[i] = p(1e9, 1e9); dp[0] = p(1, 0);
    for(auto i : ord){
        for(int j=0; j<n; j++) if(!(i & (1 << j))) {
            int k = (i | (1 << j));
            if(dp[i].y+a[j] <= s) dp[k] = min(dp[k], p(dp[i].x, dp[i].y+a[j]));
            else dp[k] = min(dp[k], p(dp[i].x+1, a[j]));
        }
    }
    cout << (int)dp[(1 << n)-1].x;
}