louisfghbvc的部落格

思路: 本來想要dp 然後紀錄，然而，這題用暴力法就搞定， 遞迴一直做，全部都找找看貨櫃數量是否等於y，如果等於y再看是否等於最大載重，兩者都是就輸出答案。

這題測資真的水，用剛剛好最大載重，不用不超過的判斷就能過。.....

代碼:

1. #include <cstring>  
2. #include <stack>  
3. #include <iostream>  
4.   
5. using namespace std;  
6. int w, y, n;  
7. int arr[105], ans[105][2];  
8. bool ok;  
9. void dfs(int i, int sum, int d){  
10.     if(ok)  
11.         return;  
12.     for(; i < n; ++i){  
13.         ans[d][0] = i;  
14.         sum += arr[i];  
15.         if(d != y - 1)  
16.             dfs(i + 1, sum, d + 1);  
17.         else{  
18.             if(sum == w){  
19.                 cout << "k" << ans[0][0];  
20.                 for(int k = 1; k < y; ++k)  
21.                     cout << ",k" << ans[k][0];  
22.                 cout << endl;  
23.                 ok = true;  
24.                 return;  
25.             }  
26.             else if(sum < w){  
27.                 if(ans[y][1] < sum){  
28.                     ans[y][1] = sum;  
29.                     for(int k = 0; k < y; ++k)  
30.                         ans[k][1] = ans[k][0];  
31.                 }  
32.             }  
33.         }  
34.         sum -= arr[i];  
35.     }  
36. }  
37. int main()  
38. {  
39.   
40.   
41.     while(cin >> w){  
42.         cin.ignore();  
43.         cin >> y;  
44.         cin.ignore();  
45.         cin >> n;  
46.         memset(ans, 0, sizeof(ans));  
47.         for(int i = 0; i < n; ++i){  
48.             cin.ignore();  
49.             cin >> arr[i];  
50.         }  
51.         ok = false;  
52.         dfs(0, 0, 0);  
53.         if(ok);  
54.         else{  
55.             cout << "k" << ans[1][0];  
56.             for(int k = 1; k < y; ++k)  
57.                 cout << ",k" << ans[1][k];  
58.             cout << endl;  
59.         }  
60.     }  
61.     return 0;  
62. }