USACO 5.3 Milk Measuring

Brutal force DFS search with a lot of pruning. The search has N passes, and it starts from 1 pail, then 2 pails, etc and up to N pails. For each pass, use memorization and pruning to avoid hitting unnecessary search space. The passes are deepened via DFS, and we return once we gets a hit in a given pass as the question was asking the smallest set of pails.

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int Q, N, total;
vector<int> pails, ans, cur;
bool found = false;

void dfs(int depth, int index, int left) {
    if (depth == total) {
        if (!left) {
            found = true;
            // dfs does not guarantee smallest order, so
            // keep this and compare with a future solution.
            ans = cur;
        }
        return;
    }
    int current = pails[index];
    // not feasible.
    if (index >= N || left < current) return;
    // current search is no smaller than existing solution.
    if (found && current > ans[depth]) return;
    cur[depth] = current;
    for (int i = 1; i <= left / current; i++) {
        dfs(depth + 1, index + 1, left - i * current);
    }
    dfs(depth, index + 1, left);
}

int main(){
    ifstream fin("milk4.in");
    ofstream fout("milk4.out");
    fin >> Q >> N;
    
    pails = cur = vector<int>(N, 0);
    for (int i = 0; i < N; i++) {
        fin >> pails[i];
    }
    sort(pails.begin(), pails.end());
    
    for (total = 1; total <= N; ++total) {
        dfs(0, 0, Q);
        if (found) break;
    }
    fout << total; cout << total;
    for (int i = 0; i < total; i++) {
        fout << " " << ans[i]; cout << " " << ans[i];
    }
    fout << endl;cout << endl;
    return 0;