第19 （分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。 他打算选择一些蛋糕装入盒子，

19（魔法数字）小 H 的魔法数字是 4。给定n，他希望用若干个 4 进行若干次加法、减法和整除运算得到 n。但由于小 H 计算能力有限，计算过程中只能出现不超过M = 10000 的正整数。求至少可能用到多少个 4。bQj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

例如，当 n = 2 时，有 2 = (4 + 4)/4，用到了 3 个 4，是最优方案。bQj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

试补全程序。bQj100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1. #include <iostream> 
2.  
3. #include <cstdlib> 
4.  
5. #include <climits> 
6.  
7. using namespace std; 
8.  
9. const int M = 10000; 
10.  
11. bool Vis[M + 1]; 
12.  
13. int F[M + 1]; 
14.  
15. void update(int &x, int y) { 
16.  
17. if (y < x) 
18.  
19. x = y; 
20.  
21. } 
22.  
23. int main() { 
24.  
25. int n; 
26.  
27. cin >> n; 
28.  
29. for (int i = 0; i <= M; i++) 
30.  
31. F[i] = INT_MAX; 
32.  
33. ①; 
34.  
35. int r = 0; 
36.  
37. while (②) { 
38.  
39. r++; 
40.  
41. int x = 0; 
42.  
43. for (int i = 1; i <= M; i++) 
44.  
45. if (③) 
46.  
47. x = i; 
48.  
49. Vis[x] = 1; 
50.  
51. for (int i = 1; i <= M; i++) 
52.  
53. if (④) { 
54.  
55. int t = F[i] + F[x]; 
56.  
57. if (i + x <= M) 
58.  
59. update(F[i + x], t); 
60.  
61. if (i != x) 
62.  
63. update(F[abs(i - x)], t); 
64.  
65. if (i % x == 0) 
66.  
67. update(F[i / x], t); 
68.  
69. if (x % i == 0) 
70.  
71. update(F[x / i], t); 
72.  
73. } 
74.  
75. } 
76.  
77. cout << F[n] << endl; 
78.  
79. return 0; 
80.  
81. }