However, test case 8 caused TLE ( 2sec. ) .
Is there other solution? Or I must improve my backtracking algorithm?
If you already solved it, plz help me.
[Problem Statement]
Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for the cows. Help Farmer John feed his cows so they stay healthy while minimizing the number of scoops that a cow is fed.
Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements.
Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data.
PROGRAM NAME: holstein
INPUT FORMAT
Line 1: integer V (1 <= V <= 25), the number of types of vitamins
Line 2: V integers (1 <= each one <= 1000), the minimum requirement for each of the V vitamins that a cow requires each day
Line 3: integer G (1 <= G <= 15), the number of types of feeds available
Lines 4..G+3: V integers (0 <= each one <= 1000), the amount of each vitamin that one scoop of this feed contains. The first line of these G lines describes feed #1; the second line describes feed #2; and so on.
SAMPLE INPUT (file holstein.in)
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399
OUTPUT FORMAT
The output is a single line of output that contains:
the minimum number of scoops a cow must eat, followed by:
a SORTED list (from smallest to largest) of the feed types the cow is given
SAMPLE OUTPUT (file holstein.out)
2 1 3
Code: Select all
------ Data for Run 8 ------
20
924 519 510 589 901 627 827 814 520 725 674 709 777 512 540 731 695 801 984 517
12
143 197 55 68 193 181 88 163 109 98 159 36 197 139 45 176 34 128 93 0
83 25 61 46 5 46 66 5 44 47 100 93 180 176 51 198 50 21 69 119
126 54 27 100 145 29 123 2 82 95 148 109 69 106 99 105 142 89 36 27
13 144 70 120 170 129 195 15 86 29 24 134 37 147 161 168 123 0 71 114
181 94 165 119 198 30 173 25 93 130 126 62 85 34 0 170 131 49 171 11
24 108 110 154 55 123 78 74 23 181 54 73 91 173 42 152 83 104 6 132
114 67 169 73 145 152 122 80 162 39 95 139 167 167 16 80 75 36 126 106
121 108 168 194 52 88 111 187 118 39 53 103 139 108 30 76 57 136 198 43
45 107 113 3 0 121 162 169 73 45 86 12 70 122 40 149 184 100 135 60
77 154 97 176 186 164 3 147 65 29 119 8 41 166 3 69 188 90 97 35
106 16 167 192 107 170 30 164 92 175 107 60 118 172 57 141 152 55 15 14
198 83 112 82 94 38 176 54 179 3 104 48 113 121 12 106 50 7 26 25
----------------------------
