去哪儿。编程第二题，怎么做啊，求解答。

参考博客 http://blog.csdn.net/jiejinquanil/article/details/52684449

public int Night(int[] nums){ int len=nums.length; int money=nums[len-1]; int night=0,sum=0; int[] prices =new int[len-1]; if(len==1)return -1; else{ for(int i=0;i<=len-2;i++){ prices[i]=nums[i]; } } Arrays.sort(prices); if(prices[0]>money)return -1; else { for(int i=len-2;i>=0&&money>0;i--){ night=money/prices[i]; money=money-night*prices[i]; sum=sum+night; } } return sum; } 可以这样做吗？

public class Main4 { static Integer res = Integer.MAX_VALUE; public static void main(String[] args) { int[] n = {1,2,3,4,6,2,5,6}; ArrayList<Integer> list = new ArrayList<>(); f(n,0,0,0); System.out.println(res); } private static void f(int[] n, int idx, int tmp, int tmpr){ if(tmp == n[n.length - 1] && tmpr < res){ res = tmpr; } if(tmp > n[n.length - 1] || idx == n.length - 2){ return; } if(idx + 1 < n.length - 1){ f(n,idx + 1, tmp, tmpr); f(n,idx + 1, tmp += n[idx], tmpr + 1); } } }

参考大神的，改了改 贪心或者说是dfs，只要不超时，应该全AC #include<iostream> #include<vector> #include<algorithm> using namespace std; int res = 0x7fffffff; void dfs(vector<int> v, int money, int k, int n) { if (money == 0) { res = res>k?k:res; return; } if (money < 0 || n < 0 || k > res) return; for (int i = money / v[n]; i >= 0; i--) dfs(v, money - i * v[n], k + i, n - 1); } int main() { int n; vector<int> v; int money; while (cin >> n) { v.push_back(n); } money = v[v.size() - 1]; v.pop_back(); sort(v.begin(), v.end()); int days = 0; dfs(v, money, 0, v.size()-1); if (res == 0x7fffffff) res = -1; cout << res; //system("pause"); return 0; }

贪心AC了

贪心算法，AC83%： #include <iostream> #include <vector> #include <algorithm>   #include <string> #include <sstream> using namespace std; bool SortByM1(const int &v1, const int &v2)  { return v1 > v2; } //main int main(){ vector<int> vecPrice; int nMoney; int nTemp; int nCount = 0; int nCurrentNumber = 0; string strLine;  getline(cin, strLine);  stringstream iss(strLine);  for (int i; iss >> i; vecPrice.push_back(i)); nMoney = vecPrice.back(); vecPrice.pop_back(); //降序排列 sort(vecPrice.begin(), vecPrice.end(), SortByM1); vector<int>::const_iterator iter = vecPrice.begin(); for (; iter != vecPrice.end(); iter++){ nCurrentNumber = *iter; while (nCurrentNumber<=nMoney) //贪心算法 { nCount++; nMoney -= nCurrentNumber; } if (nMoney==0) { break; } } if (nCount==0||nMoney>0) cout << "-1" << endl; else    cout << nCount << endl; }

确实是 找钱问题，参考了下，感觉现在应该没问题，好像还不用排序。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; vector<int> v; int money; while (cin >> n) { v.push_back(n); } money = v[v.size() - 1]; v.pop_back(); //sort(v.begin(), v.end()); int length = v.size(); int *days = new int[money + 1]; int *value = new int[money + 1]; days[0] = 0; for (int i = 1; i <= money; i++) { int min = i; int used = 0; for (int j = 0; j < length; j++) { if (i >=v[j]) { if (days[i - v[j]] + 1 <= min && (i == v[j] || value[i - v[j]] != 0)) { min = days[i - v[j]] + 1; used = v[j]; } } } days[i] = min; value[i] = used; } if (value[money] == 0) cout << -1 << endl; else cout << days[money] << endl; //system("pause"); return 0; }

有兄弟收到面试通知没

找钱问题

楼主收到面试通知了吗，据说当天就给，第二天就面

可以使用递归来解决，AC83%

可不可以住重复的酒店

package qunar; import java.util.Scanner; public class Main2 { static int rel =9999; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); String s; while(in.hasNext()){ s = in.nextLine(); rel = 9999; gs(s); if(rel != 9999){ System.out.println(rel); }else{ System.out.println("-1"); } } } public static void gs(String s){ String[] ar = s.split(" "); int n = ar.length; int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = Integer.valueOf(ar[i]); } dp(arr,n-2,arr[n-1],0); } public static void dp(int[] arr,int now,int money,int day){ if(money < 0){ return; } if(money == 0){ if(day < rel){ rel = day; return ; } } if(money%arr[now] == 0){ if(money/arr[now] < rel){ rel = money/arr[now]+day; return; } }else{ for(int i=now;i>=0;i--){ if(money>=arr[i]){ dp(arr,i,money-arr[i],day+1); } } } } } 有一些多余的地方

67%没办法完美

完全背包 HDU1114，有很多题解，百度一下。

这不就是一个数组中最少数之和等于最后一个元素的问题吗！

是个动态规划问题，只用贪心可以过83%

http://blog.csdn.net/kangroger/article/details/36036101，，，这个你懂了，就会做去哪网的题了

用dfs过了。。

为什么是最少天数而不是最多天数。。