给定一个整数，求解该整数最少能用多少个Fib数字相加得到

66 阅读 0 评论 44 点赞

我是靠谱客的博主勤劳指甲油，这篇文章主要介绍给定一个整数，求解该整数最少能用多少个Fib数字相加得到，现在分享给大家，希望可以做个参考。

一，问题描述

给定一个整数N，求解该整数最少能用多少个Fib数字相加得到

Fib数列，就是如： 1，1，2，3，5，8，13....

Fib数列，满足条件：Fib(n)=Fib(n-1)+Fib(n-2) Fib(0)=1 Fib(1)=1；Fib数字，就是Fib数列中的某个数。

比如70 = 55+13+2，即一共用了3个fib数字得到

二，问题求解

①求出所有小于等于N的Fib数字

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//获得小于等于n的所有fib数
private static ArrayList<Integer> getFibs(int n){
ArrayList<Integer> fibs = new ArrayList<Integer>();
int fib1 = 1;
int fib2 = 1;
fibs.add(fib1);
fibs.add(fib2);
int fibn;
while((fibn = fib1 + fib2) <= n)
{
fibs.add(fibn);
fib1 = fib2;
fib2 = fibn;
}
return fibs;
}

②其实这个问题，可以转化为一个"完全0-1背包问题"。

所谓完全0-1背包问题是指：每个物品可以重复地选择。而这里，每个Fib数字则可以重复地选择。

如：70=34+34+2，34就选择了两次，fib(i) 最多可选择的次数是：N/fib(i)，也就是说：将某个Fib数字拆分成(复制成)多个相同与原来值相同的Fib数字。这样，就相当于每个数字只能够选一次，即要么选择它、要么不选择它。

这样，就将完全0-1背包问题转化成普通的0-1背包问题。

这样，就可以把上面求得的ArrayList中存在的Fib数字“扩充”成具有重复Fib数字的ArrayList

比如，对于70而言：扩充后的fib数组为：会有70个1，70/2个 2 ......

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
8, 8, 8, 8, 8, 8, 8, 8,
13, 13, 13, 13, 13, 21, 21, 21,
34, 34,
55]

根据普通0-1背包问题，对于这个问题，每次总是优先选择最靠近N的那个fib数字，然后再考虑比N次小的那个fib数字......

也就是说，每次总是尽可能地选择接近N的fib数字

其实，这相当于一个贪心问题.

因为对于贪心而言，是先做选择，这个选择在当时看起来是最优的，然后得到一个子问题。比如：对于70而言，先选择比70小的最靠近70的那个fib数：55

此时，得到的子问题就是求解 15 （70减去55）最少能用多少个Fib数字相加得到？

一点关于这个问题的贪心算法正确性的证明。

设 S={f(1)，f(2)，....f(n)}是一组不大于N的fib 数列，且S已经排序，那么f(n)是小于N 且最接近N的那个fib数。

我们要证明的则是：S的某个最优解中一定包含了f(n)

假设S(i)={f(i₁)，f(i₂),.....f(i_k-1)，f(i_k)}是N的一个最优解，并且 S(i)集合中的fib数已经从小到大排序。也就是说：S(i)是所有具有最少个fib数的集合，即，∑S(i)=N 且S(i)中包含的元素个数最少。

若 f(i_k) = f(n)，因为S(i)是最优解，而f(n)又等于S(i)中最后一个元素，故S的最优解S(i)包含了f(n)，得证。

若f(i_k) != f(n)，那么f(n)>f(i_k)，因为f(n)是最接近N的fib数，是S集合中的max。此时，我们可以运用“剪枝”思想。把 f(i_k)从 S(i)中删除，并将 f(n) 添加到S(i)中。设剪枝后的集合为S″(i)

如果S(i)中没有重复的元素，删除f(i_k) 并添加了 f(n)之后，∑S″(i)>N。那么，为什么使∑S^″(i)=N，就需要再从S^″(i)中删除某些元素。

此时，S^″(i) 是一个包含了f(n)且元素个数比 S(i)更少的集合。因此，它是一个更优的解。

比如 70=55+13+2 比 70=34+21+13+2 更优。

如果S(i)中有重复的元素，我们需要证明的是S^″(i)中的元素个数最多和 S(i)中的元素一样多，但是不会比S(i)更多。

这个证明会用到 Fib数列的性质：Fib(n)=Fib(n-1)+Fib(n-2)

先举个例子，70=34+34+2 与 70=55+13+2，在这里f(n)-f(k)=55-34=21

而，fib(n)=fib(n-1)+fib(n-3)+fib(n-5)+....+fib(k)

（具体的证明不会啊。有大神可指教啊。。。）总之，应该用贪心算法是正确的。

关于证明，还可参考：找换硬币问题中的证明。感觉应该很类似。

关于贪心算法正确性的证明，可参考从活动选择问题看动态规划和贪心算法的区别与联系中的关于“活动选择问题”的贪心正确性证明分析。

而对于DP，是先寻找子问题的最优解，然后再做选择。

三，参考资料

部分背包问题的贪心算法正确性证明

某种找换硬币问题的贪心算法的正确性证明

整个完整代码：

复制代码

1 import java.util.ArrayList;
 2
 3 public class Solution {
 4
 5
//获得小于等于n的所有fib数
 6
private static ArrayList<Integer> getFibs(int n){
 7
ArrayList<Integer> fibs = new ArrayList<Integer>();
 8
int fib1 = 1;
 9
int fib2 = 1;
10
11 
fibs.add(fib1);
12 
fibs.add(fib2);
13
14
int fibn;
15
while((fibn = fib1 + fib2) <= n)
16 
{
17 
fibs.add(fibn);
18
fib1 = fib2;
19
fib2 = fibn;
20 
}
21
return fibs;
22 
}
23
24
//将之转化成 可重复选择的 0-1 背包问题
25
private static ArrayList<Integer> augument(ArrayList<Integer> fibs, int n){
26
ArrayList<Integer> dupfibs = new ArrayList<Integer>();
27
for (Integer integer : fibs) {
28
int times = n/integer;//每个fib数字最多可选择多少次
29
for(int i = 1; i <= times; i++)
30
dupfibs.add(integer);//"拆分"fib数字
31 
}
32
return dupfibs;
33 
}
34
35
//贪心算法,每次贪心选择最靠近
36
private static int dp(ArrayList<Integer> dupfibs, int n){
37
int currentSum = 0;
38
int count = 0;//需要使用的fib数字 个数
39
while(currentSum != n){
40
for(int i = dupfibs.size()-1; i >= 0; i--){
41
currentSum += dupfibs.get(i);
42
count++;//表示选择了这个fib数
43
if(currentSum > n)
44 
{
45
currentSum -= dupfibs.get(i);
46
count--;//选择的fib数相加之后越过了n，因此不能选择它
47 
}
48 
}
49 
}
50
return count;
51 
}
52
53
//功能入口
54
public static int function(int n){
55
ArrayList<Integer> fibs = getFibs(n);
56
fibs = augument(fibs, n);
57
int result = dp(fibs, n);
58
return result;
59 
}
60
61
//test
62
public static void main(String[] args) {
63
int result = function(70);
64 
System.out.println(result);
65 
}
66 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 1 import java.util.ArrayList;
 2
 3 public class Solution {
 4
 5
//获得小于等于n的所有fib数
 6
private static ArrayList<Integer> getFibs(int n){
 7
ArrayList<Integer> fibs = new ArrayList<Integer>();
 8
int fib1 = 1;
 9
int fib2 = 1;
10
11 
fibs.add(fib1);
12 
fibs.add(fib2);
13
14
int fibn;
15
while((fibn = fib1 + fib2) <= n)
16 
{
17 
fibs.add(fibn);
18
fib1 = fib2;
19
fib2 = fibn;
20 
}
21
return fibs;
22 
}
23
24
//将之转化成 可重复选择的 0-1 背包问题
25
private static ArrayList<Integer> augument(ArrayList<Integer> fibs, int n){
26
ArrayList<Integer> dupfibs = new ArrayList<Integer>();
27
for (Integer integer : fibs) {
28
int times = n/integer;//每个fib数字最多可选择多少次
29
for(int i = 1; i <= times; i++)
30
dupfibs.add(integer);//"拆分"fib数字
31 
}
32
return dupfibs;
33 
}
34
35
//贪心算法,每次贪心选择最靠近
36
private static int dp(ArrayList<Integer> dupfibs, int n){
37
int currentSum = 0;
38
int count = 0;//需要使用的fib数字 个数
39
while(currentSum != n){
40
for(int i = dupfibs.size()-1; i >= 0; i--){
41
currentSum += dupfibs.get(i);
42
count++;//表示选择了这个fib数
43
if(currentSum > n)
44 
{
45
currentSum -= dupfibs.get(i);
46
count--;//选择的fib数相加之后越过了n，因此不能选择它
47 
}
48 
}
49 
}
50
return count;
51 
}
52
53
//功能入口
54
public static int function(int n){
55
ArrayList<Integer> fibs = getFibs(n);
56
fibs = augument(fibs, n);
57
int result = dp(fibs, n);
58
return result;
59 
}
60
61
//test
62
public static void main(String[] args) {
63
int result = function(70);
64 
System.out.println(result);
65 
}
66 }