Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:显然是O(n^2)的DPIn Reply To:Re:显然是O(n^2)的DP Posted by:sad at 2005-05-05 11:58:23 public int findMin(int weight) { int min[] = new int[grossWeight+1]; for(int i=0;i<=grossWeight;i++){ min[i] = 999999; } if(weight==0) return 0; if(weight<0) return -1; else if(min[weight]!=999999) return min[weight]; for(int i=0;i<sort;i++){ int temp = findMin(weight-coins[i].getWeight()); if(temp!=-1 && temp+coins[i].getValue()<min[weight]){ min[weight] = temp + coins[i].getValue(); } } if(min[weight]==999999) return -1; else return min[weight]; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator