USACO Training Section 2.1 Healthy Holsteins

英語の原題
中国語の翻訳
大体の問題:
乳牛は多種のビタミンを補充する必要があって、農夫の手元にN種類の丸薬があって、それぞれ一定のビタミンを補充することができて、すべての丸薬は毎日1粒しか食べられなくて、少なくともどれだけの丸薬が必要かを聞いて、しかも丸薬の辞書の順序の最小の配列を出力することを要求します.
クラシックな0-1リュックサックの問題は、もちろん非再帰的に遡ることができますが、ここでは直接再帰することができます.再帰の順序に注意して、まず食べることを選んで、それから食べないことを選んでください.食べてしまえばいいので、食べなくてもいいです.辞書順が一番小さいものを出力するだけで、食べない場合は1つの錠剤数を検索し続けると必ず減少しないので、2つの辞書順が上昇するので、枝を切ることができます.また、ここで枝を切るときはデータを復元する必要があることに注意してください.

/*
ID: blackco3
TASK: holstein
LANG: C++
*/
#include <fstream>
#include <memory.h>

#define _max_vitamin_ 25
#define _max_feed_ 15
using namespace std;
int require[_max_vitamin_], feeds[_max_feed_][_max_vitamin_] ;
int n_vitamin, n_feed ;
int trace[_max_feed_], uses[_max_feed_], n_need=_max_feed_ ;

void get_need(int feed, int used)
{
	if( feed>=n_feed || used>=n_need )
		return ;
	int need_more=false ;
	for( int i=0; i<n_vitamin; i++ ){
		require[i] -= feeds[feed][i] ;
		if( require[i]>0 )
			need_more=true ;
	}
	uses[used++]=feed ;
	if( !need_more ){
		if( used<n_need ) {
			n_need=used ;
			memcpy( trace, uses, sizeof(int)*used );
		}
		for( int i=0; i<n_vitamin; i++ )
			require[i] += feeds[feed][i] ;
	} else {
		get_need( feed+1, used );
		for( int i=0; i<n_vitamin; i++ )
			require[i] += feeds[feed][i] ;
		get_need( feed+1, --used ) ;
	}
}

int main() {
    ofstream fout ("holstein.out");
    ifstream fin ("holstein.in");
	fin >> n_vitamin ;
	for( int i=0; i<n_vitamin; i++ )
		fin >> require[i] ;
	fin >> n_feed ;
	for( int i=0; i<n_feed; i++ )
		for( int j=0; j<n_vitamin; j++ )
			fin >> feeds[i][j] ;
	get_need(0,0);
	fout << n_need ;
	for( int i=0; i<n_need; i++ )
		fout << " " << trace[i]+1 ;
	fout << endl; 
	return 0;
}