USACO 3.4 Raucous Rockers

Typical BackPack problem but with the limited scale of test data, a straight forward brutal force search could do it. The search space is the permutation of subsets of all songs, for each song we have two choice - choose or not choose. Iterate the sequence under the constraint of ordering.

#include <vector>
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

int N /* songs */, M /* disks */, T /* disk capacity */;
vector<int> songs;
vector<int> disks;

int main() {
    ifstream fin("rockers.in");
    ofstream fout("rockers.out");
    fin >> N >> T >> M;
    songs = vector<int>(N, 0);
    for (int i = 0; i < N; ++i) {
        fin >> songs[i];
    }
    disks = vector<int>(M, 0);
    int ans = INT_MIN;
    int upper = 1 << N;
    for (int i = 1; i <= upper; ++i) {
        std::fill(disks.begin(), disks.end(), 0);
        int idx = 0, sum = 0;
        for (int j = 0; j < N; ++j) {
            bool pick = (1 << j) & i;
            if (!pick) continue;
            for(int k = idx; k < M; ++k, ++idx){
                if(disks[k] + songs[j] <= T){
                    disks[k] += songs[j];
                    ++sum;
                    break;
                }
            }
        }
        ans = std::max(ans, sum);
    }
    
    cout << ans << endl;
    fout << ans << endl;
}