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