P1460 健康的荷斯坦奶牛

May 11, 2026 · 8 分钟阅读 · 深度优先搜索枚举回溯 ·

文章目录

题目信息

字段	内容
题号	P1460
难度	普及-
知识点	深度优先搜索、枚举、搜索与回溯

题目描述

农夫 John 的奶牛需要补充维生素。已知每种维生素的每日最低需求量，以及每种饲料中各维生素的含量。

给定 g 种饲料，每种饲料可以无限使用，但每种饲料最多使用一次。请找出满足所有维生素需求的最少饲料种类数，并输出使用的饲料编号。

输入格式

第一行：整数 n，表示维生素种类数
第二行：n 个整数，表示每种维生素的每日最低需求量
第三行：整数 g，表示饲料种类数
接下来 g 行：每行 n 个整数，第 i 行第 j 列表示第 i 种饲料中维生素 j 的含量

输出格式

第一行：最少需要的饲料种类数 k
第二行：使用的 k 种饲料的编号（按升序排列）

样例

输入 #1：

4
100 200 300 400
3
200 300 150 500
300 100 300 500
600 700 400 600

输出 #1：

2 2 3

解题思路

核心思想

这是一道典型的 DFS 枚举 + 剪枝 问题。

关键观察：

每种饲料要么选，要么不选（01 组合）
需要找满足条件的最小选择数
按字典序输出方案（题目要求）

算法流程：

DFS(id, k):
    // id: 当前考虑第 id 种饲料
    // k: 已经被选中的饲料数量

    if id > g:  // 所有饲料都考虑完了
        if 满足需求 且 k < 最小数量:
            更新答案
        return

    // 选第 id 种饲料
    c[k+1] = id
    DFS(id+1, k+1)

    // 不选第 id 种饲料
    DFS(id+1, k)

判断函数 `check(k)`

检查当前选择的 k 种饲料是否满足所有维生素需求：

bool check(int k) {
    for each vitamin i:
        sum = sum of vitamin i from selected feeds
        if sum < required[i]: return false
    return true
}

剪枝策略

数量剪枝：只记录比当前最优解更少的方案
提前终止：找到第一个满足条件的方案后继续搜索（保证字典序）

完整代码

C++

#include <bits/stdc++.h>

namespace {

constexpr int kMaxG = 15;  // 最大饲料种类数
constexpr int kMaxN = 25;  // 最大维生素种类数
constexpr int kInf = 0x3f3f3f3f;  // 无穷大

// 每种维生素的最低需求量
int required[kMaxN + 1];
// 各饲料中维生素含量：feed[i][j] = 第 i 种饲料中维生素 j 的含量
int feed[kMaxG + 1][kMaxN + 1];
// 答案：选择的饲料数量和编号
int answer_count;
int answer[kMaxG + 1];
// 当前选择方案
int current[kMaxG + 1];
// 当前最优的饲料数量
int min_count;

// 维生素种类数和饲料种类数
int vitamin_count;
int feed_count;

/**
 * 检查当前选择的 k 种饲料是否满足所有维生素需求
 * @param k 选择的饲料数量
 * @return true 表示满足需求
 */
bool CheckSolution(int k) {
    for (int i = 1; i <= vitamin_count; ++i) {
        int sum = 0;
        for (int j = 1; j <= k; ++j) {
            sum += feed[current[j]][i];
        }
        if (sum < required[i]) {
            return false;
        }
    }
    return true;
}

/**
 * DFS 枚举所有可能的饲料组合
 * @param id 当前考虑的饲料编号
 * @param k 已经选择的饲料数量
 */
void DfsSearch(int id, int k) {
    if (id > feed_count) {
        if (CheckSolution(k) && k < min_count) {
            min_count = k;
            for (int i = 1; i <= min_count; ++i) {
                answer[i] = current[i];
            }
        }
        return;
    }

    // 选择第 id 种饲料
    current[k + 1] = id;
    DfsSearch(id + 1, k + 1);

    // 不选第 id 种饲料
    DfsSearch(id + 1, k);
}

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> vitamin_count;
    for (int i = 1; i <= vitamin_count; ++i) {
        std::cin >> required[i];
    }

    std::cin >> feed_count;
    for (int i = 1; i <= feed_count; ++i) {
        for (int j = 1; j <= vitamin_count; ++j) {
            std::cin >> feed[i][j];
        }
    }

    min_count = kInf;
    DfsSearch(1, 0);

    std::cout << min_count << " ";
    for (int i = 1; i <= min_count; ++i) {
        std::cout << answer[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const (
	maxG = 15
	maxN = 25
	inf  = 0x3f3f3f3f
)

var (
	required [maxN + 1]int    // 维生素需求量
	feed     [maxG + 1][maxN + 1]int  // 各饲料维生素含量
	answer   [maxG + 1]int
	current  [maxG + 1]int
	minCount int = inf
	vitaminCount, feedCount int
)

// checkSolution 检查当前选择的 k 种饲料是否满足需求
func checkSolution(k int) bool {
	for i := 1; i <= vitaminCount; i++ {
		sum := 0
		for j := 1; j <= k; j++ {
			sum += feed[current[j]][i]
		}
		if sum < required[i] {
			return false
		}
	}
	return true
}

// dfsSearch DFS 枚举所有组合
func dfsSearch(id, k int) {
	if id > feedCount {
		if checkSolution(k) && k < minCount {
			minCount = k
			for i := 1; i <= minCount; i++ {
				answer[i] = current[i]
			}
		}
		return
	}

	// 选第 id 种饲料
	current[k+1] = id
	dfsSearch(id+1, k+1)

	// 不选第 id 种饲料
	dfsSearch(id+1, k)
}

func main() {
	in := bufio.NewReader(os.Stdin)

	fmt.Fscan(in, &vitaminCount)
	for i := 1; i <= vitaminCount; i++ {
		fmt.Fscan(in, &required[i])
	}

	fmt.Fscan(in, &feedCount)
	for i := 1; i <= feedCount; i++ {
		for j := 1; j <= vitaminCount; j++ {
			fmt.Fscan(in, &feed[i][j])
		}
	}

	dfsSearch(1, 0)

	fmt.Print(minCount)
	for i := 1; i <= minCount; i++ {
		fmt.Print(" ", answer[i])
	}
	fmt.Println()
}

Java

import java.io.*;
import java.util.*;

public class Main {
    private static final int MAX_G = 15;
    private static final int MAX_N = 25;
    private static final int INF = 0x3f3f3f3f;

    private static int[] required = new int[MAX_N + 1];
    private static int[][] feed = new int[MAX_G + 1][MAX_N + 1];
    private static int[] answer = new int[MAX_G + 1];
    private static int[] current = new int[MAX_G + 1];
    private static int minCount = INF;

    private static int vitaminCount;
    private static int feedCount;

    /** 检查当前选择的 k 种饲料是否满足需求 */
    private static boolean checkSolution(int k) {
        for (int i = 1; i <= vitaminCount; i++) {
            int sum = 0;
            for (int j = 1; j <= k; j++) {
                sum += feed[current[j]][i];
            }
            if (sum < required[i]) {
                return false;
            }
        }
        return true;
    }

    /** DFS 枚举所有组合 */
    private static void dfsSearch(int id, int k) {
        if (id > feedCount) {
            if (checkSolution(k) && k < minCount) {
                minCount = k;
                for (int i = 1; i <= minCount; i++) {
                    answer[i] = current[i];
                }
            }
            return;
        }

        // 选第 id 种饲料
        current[k + 1] = id;
        dfsSearch(id + 1, k + 1);

        // 不选第 id 种饲料
        dfsSearch(id + 1, k);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        vitaminCount = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= vitaminCount; i++) {
            required[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        feedCount = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= feedCount; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= vitaminCount; j++) {
                feed[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfsSearch(1, 0);

        System.out.print(minCount);
        for (int i = 1; i <= minCount; i++) {
            System.out.print(" " + answer[i]);
        }
        System.out.println();
    }
}

Python

import sys

MAX_G = 15
MAX_N = 25
INF = 0x3f3f3f3f

required = [0] * (MAX_N + 1)
feed = [[0] * (MAX_N + 1) for _ in range(MAX_G + 1)]
answer = [0] * (MAX_G + 1)
current = [0] * (MAX_G + 1)
min_count = INF

vitamin_count = 0
feed_count = 0


def check_solution(k: int) -> bool:
    """检查当前选择的 k 种饲料是否满足需求"""
    for i in range(1, vitamin_count + 1):
        total = 0
        for j in range(1, k + 1):
            total += feed[current[j]][i]
        if total < required[i]:
            return False
    return True


def dfs_search(id: int, k: int) -> None:
    """DFS 枚举所有组合"""
    global min_count

    if id > feed_count:
        if check_solution(k) and k < min_count:
            min_count = k
            for i in range(1, min_count + 1):
                answer[i] = current[i]
        return

    # 选第 id 种饲料
    current[k + 1] = id
    dfs_search(id + 1, k + 1)

    # 不选第 id 种饲料
    dfs_search(id + 1, k)


def main() -> None:
    global vitamin_count, feed_count

    data = sys.stdin.read().split()
    it = iter(data)

    vitamin_count = int(next(it))
    for i in range(1, vitamin_count + 1):
        required[i] = int(next(it))

    feed_count = int(next(it))
    for i in range(1, feed_count + 1):
        for j in range(1, vitamin_count + 1):
            feed[i][j] = int(next(it))

    dfs_search(1, 0)

    sys.stdout.write(str(min_count))
    for i in range(1, min_count + 1):
        sys.stdout.write(" " + str(answer[i]))
    sys.stdout.write("\n")


if __name__ == "__main__":
    main()

JavaScript

'use strict';

const MAX_G = 15;
const MAX_N = 25;
const INF = 0x3f3f3f3f;

let required;
let feed;
let answer;
let current;
let minCount;

let vitaminCount;
let feedCount;

function checkSolution(k) {
    for (let i = 1; i <= vitaminCount; i++) {
        let sum = 0;
        for (let j = 1; j <= k; j++) {
            sum += feed[current[j]][i];
        }
        if (sum < required[i]) {
            return false;
        }
    }
    return true;
}

function dfsSearch(id, k) {
    if (id > feedCount) {
        if (checkSolution(k) && k < minCount) {
            minCount = k;
            for (let i = 1; i <= minCount; i++) {
                answer[i] = current[i];
            }
        }
        return;
    }

    // 选第 id 种饲料
    current[k + 1] = id;
    dfsSearch(id + 1, k + 1);

    // 不选第 id 种饲料
    dfsSearch(id + 1, k);
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);

    vitaminCount = parseInt(input[0], 10);
    required = new Array(MAX_N + 1).fill(0);
    for (let i = 1; i <= vitaminCount; i++) {
        required[i] = parseInt(input[i], 10);
    }

    feedCount = parseInt(input[vitaminCount + 1], 10);
    feed = Array.from({ length: MAX_G + 1 }, () => new Array(MAX_N + 1).fill(0));
    let idx = vitaminCount + 2;
    for (let i = 1; i <= feedCount; i++) {
        for (let j = 1; j <= vitaminCount; j++) {
            feed[i][j] = parseInt(input[idx++], 10);
        }
    }

    answer = new Array(MAX_G + 1).fill(0);
    current = new Array(MAX_G + 1).fill(0);
    minCount = INF;

    dfsSearch(1, 0);

    let output = String(minCount);
    for (let i = 1; i <= minCount; i++) {
        output += " " + answer[i];
    }
    console.log(output);
}

main();

关键代码讲解

1. 枚举策略

void DfsSearch(int id, int k) {
    // 选第 id 种饲料
    current[k + 1] = id;
    DfsSearch(id + 1, k + 1);

    // 不选第 id 种饲料
    DfsSearch(id + 1, k);
}

这是一个二叉树遍历，每个节点表示"选或不选"。

2. 检查函数

bool CheckSolution(int k) {
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int j = 1; j <= k; ++j) {
            sum += feed[current[j]][i];
        }
        if (sum < required[i]) return false;
    }
    return true;
}

遍历所有维生素，累加选中饲料的含量，与需求量比较。

3. 答案更新

if (CheckSolution(k) && k < min_count) {
    min_count = k;
    for (int i = 1; i <= min_count; ++i) {
        answer[i] = current[i];
    }
}

只有更少的饲料数量才会更新答案。

复杂度分析

方法	时间复杂度	空间复杂度
DFS 枚举	`O(2^g × g × n)`	`O(g + n)`

说明：

2^g 种组合（每种饲料选或不选）
每种组合检查需要 O(g × n)
g ≤ 15，实际可解

易错点

初始值设置：min_count 要初始化为 INF（一个很大的数）
数组大小：feed[g+1][n+1] 需考虑边界
回溯状态恢复：不需要显式恢复（直接覆盖）
输出格式：第一行是数量，后面是编号，用空格分隔

类似题目

P1215 银河英雄传说（搜索）
P1618 三连击（升级版）（枚举排列）
P1100 方程求解（搜索与回溯）