USACO備考衝刺必刷題 | P1460 Healthy Holsteins

學習C++從娃娃抓起！記錄下USACO（美國信息學奧賽）備考學習過程中的題目，記錄每一個瞬間。

附上匯總貼：

#include <bits/stdc++.h>
using namespace std;
int vType, fType, p;
int v[30], f[20][30], sel[20], ans[20];
int minSelCnt = 20;
bool check(int selCnt)  // 定義維他命檢查函數
{
    for (int i=1; i<=vType; i++) {  // 依次遍歷所有維他命種類
        int sum = 0;  // 定義每種維他命的總數，每次循環初始為0
        for (int j=1; j<=selCnt; j++) {  // 依次遍歷選擇的那些飼料
            sum += f[sel[j]][i];  // sum加上選擇的飼料編號的維他命值
        }
        if (sum<v[i]) {  // 如果總和
            return false;
        }
    }
    return true;
}
void dfs(int pos, int cnt)  // 定義dfs函數，pos為飼料編號，cnt為飼料選擇的數量
{
    if (pos > fType) {  // dfs退出條件，直到選到最後一種飼料編號
        if (check(cnt) && cnt < minSelCnt) {  // 如果此時選擇的飼料的每種維他命之和大於最小維他命需要，且選擇數量小於最小選擇數量
            minSelCnt = cnt;  // 更新最小選擇數量
            for (int i=1; i<=cnt; i++) {  // 更新結果數組，即更新為選擇的飼料種類
                ans[i] = sel[i];  
            }
        }
        return;  // 一定要寫！
    }
    sel[cnt+1] = pos;  // 選擇編號為pos的飼料
    dfs(pos+1, cnt+1);  // 繼續選擇pos+1編號的飼料，cnt自增1
    sel[cnt+1] = 0;  // 不選編號為pos的飼料，不選就用0佔位（這句可以忽略，因為下一句dfs中cnt不變，下次執行後會被修改）
    dfs(pos+1, cnt);  // 繼續dfs搜索pos+1編號的飼料，但cnt不增加
}
int main()
{
    cin >> vType;  // 輸入需要的維他命種類數
    for (int i=1; i<=vType; i++) {  // 遍歷維他命種類數
        cin >> v[i];  // 輸入每種維他命的最小量
    }
    cin >> fType;  // 輸入飼料種數
    for (int i=1; i<=fType; i++) {  // for循環遍歷飼料種數
        for (int j=1; j<=vType; j++) {  // for循環遍歷維他命種類數
            cin >> f[i][j];  // 輸入這種飼料各種維他命的值
        }
    }
    dfs(1, 0);  // 使用dfs搜索，起始飼料編號為1，0種選擇
    cout << minSelCnt << " ";
    for (int i=1; i<=minSelCnt; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

【運行結果】

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399
2 1 3