这是一个创建于 2444 天前的主题，其中的信息可能已经有所发展或是发生改变。
碰到的一个 PHP 面试题
例如有个数组：
$arr = [1,2,3,4,5,6,7,8,9];
求出该数组任意个元素的组合，并不重复
类似
$result = [
[1,2],
[1,3],
[1,4],
[1,5],
[1,2,3],
[2,3,4],
...
...
];
-------------------------------------分割线-------------------------------------
扩展：
给出一个值，如：
$n = 20.2
求出上述数组中，任意个元素的组合相加后与该值最接近的组合
也就是类似说的背包问题
有大佬有解法吗，当时没有想到好的解法
例如有个数组：
$arr = [1,2,3,4,5,6,7,8,9];
求出该数组任意个元素的组合，并不重复
类似
$result = [
[1,2],
[1,3],
[1,4],
[1,5],
[1,2,3],
[2,3,4],
...
...
];
-------------------------------------分割线-------------------------------------
扩展：
给出一个值，如：
$n = 20.2
求出上述数组中，任意个元素的组合相加后与该值最接近的组合
也就是类似说的背包问题
有大佬有解法吗，当时没有想到好的解法
 |
1
sean10 2018-03-15 20:55:04 +08:00 via Android
|
 |
2
ipwx 2018-03-15 21:07:28 +08:00
题目要求输出所有组合。所以数组长度必然不大，毕竟最后的存储空间要达到 sizeof(int) * n * 2^n 字节。所以我们假设 n < 32。所以可以 for (unsigned int i=0; i<(1<<n); ++i)，然后在循环里面根据 i 的二进制位（是否为 1 ），选择元素，生成列表。
|
 |
3
msg7086 2018-03-16 02:37:03 +08:00
扩展不是背包问题吧？
|
|
6
msg7086 2018-03-16 09:21:20 +08:00
把数字转换成二进制，是 1 的位就选出对应的数字下标，是 0 就不选，然后本题应该是要去掉只有一个数的数组吧，过滤一下就好了。
|
Select Language