健康なハスタン乳牛-USACO-USACO階段-第2章.より大きな課題

タイトルの説明
2.1.4 Healthy Holsteins健康なハスタン乳牛
(holstein.pas/c/cpp)
農民のJOHNは世界で最も健康な乳牛を持っていることを誇りに思っている.彼は飼料ごとに含まれる牛に必要な最低のビタミン量がどれだけあるか知っている.農夫が牛を飼って健康を維持し、牛に与える飼料の種数を最小限に抑えるのを助けてください.
牛に必要な最低ビタミン量を与え、牛に与えるのに必要な飼料の種類を出力し、必要な飼料用量を最小限に抑える.
ビタミン量は整数で表され、飼料1種につき最大1回しか牛に使用できず、データは解の存在を保証している.
書式設定
PROGRAM NAME: holstein
INPUT FORMAT:(file holstein.in)
1行目:整数V(1<=V<=25)で、必要なビタミンの種類数を表します.
2行目:V個の整数(1<=数<=1000)は、牛が毎日必要とするビタミンの最小量を表す.
3行目:1つの整数G(1<=G<=15)は、牛に餌を与えるために使用できる飼料の種数を表す.
以下G行、n行目はn飼料に含まれる各種ビタミンの量の多少を示す.
OUTPUT FORMAT:(file holstein.out)
出力ファイルには1行しかありません.
牛に必要な最小の飼料種数P
後ろにP個の数があり、選択した飼料番号(小さいものから大きいものまで)を示す.
複数の解がある場合、出力飼料番号が最小(すなわち、辞書順が最小)である.
SAMPLE INPUT

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

SAMPLE OUTPUT

2 1 3

問題解決の考え方:
どの飼料にも2つの選択肢があるからです.
遡及法で
解題手順:
1.遡及法による飼料の生成方案
2.このシナリオが実行可能かどうかをチェックする
3.実行可能で、元の答えよりも優れている場合、最小飼料種数と飼料番号を更新する
4.出力
Code:

#include
using namespace std;
int v,a[30],vt[16][30],ans[16],vis[16];
int g,num = 10000000,num1;
int check()
{
    for(int i = 1; i <= v; i++)
        if(a[i] > 0) return 0;
    return 1;
}
void work()
{
    int cnt = 0;
    for(int i = 1; i <= g; i++)
        if(vis[i] == 1) ans[++cnt] = i;
}
void dfs(int dep)
{
    if(check())
    {
        if(num1 < num)
        {
            num = num1;
            work();
            return;
        }
    }
    if(dep > g) return;
    for(int i = 1; i <= v; i++) a[i] -= vt[dep][i];
    vis[dep] = 1;
    num1++;
    dfs(dep + 1);
    for(int i = 1; i <= v; i++) a[i] += vt[dep][i];
    vis[dep] = 0;
    num1--;
    dfs(dep + 1);
}
int main()
{
    scanf("%d",&v);
    for(int i = 1; i <= v; i++) scanf("%d",&a[i]);
    scanf("%d",&g);
    for(int i = 1; i <= g; i++)
        for(int j = 1; j <= v; j++) scanf("%d",&vt[i][j]);
    dfs(1);
    printf("%d ",num);
    for(int i = 1; i <= num; i++) printf("%d ",ans[i]);
    printf("
");
    return 0;
}