题解 | #训练聪明的牛II#
训练聪明的牛II
https://www.nowcoder.com/practice/79f86360f2894f76b88d33b28a5d09b8?tpId=354&tqId=10595672&ru=/exam/oj&qru=/ta/interview-202-top/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D354
int cmp(int *a,int *b) { return *a<*b; } void dfs(int *nums,int size,int sum,int len,int *min,int *flag){ if(sum<0) return; if(sum==0){ (*min) = fmin((*min),len); *flag=1; return; } for(int i=0;i<size;i++){ int target = sum; sum-=nums[i]; dfs(nums,size,sum,len+1,min,flag); if((*flag)==1) return; sum = target; } } int minEatTimes(int* weights, int weightsLen, int totalWeight ) { int min=100000; qsort(weights,weightsLen,4,cmp); int flag=0; dfs(weights,weightsLen,totalWeight,0,&min,&flag); if(min==100000) return -1; return min; }
回溯+贪心