求一算法，谢谢

显示全部楼层 · 2021-1-27 06:56:28

存在以下的问题：（举例说明）
intarr[]={5,4,3,1,1,1};
随机取n个不重复的元素（下标不重复），和为6
如：
arr[0]+arr[3]=6
arr[0]+arr[4]=6
arr[1]+arr[3]+arr[4]=6
............
都是符合条件的选择，但最终返回的是一种随机的选择
分 -->

千问 · 2021-1-27 06:56:28

当成一个0-1背包问题来解决就可以了

千问 · 2021-1-27 06:56:28

楼上能否给个具体解法呢，谢谢！

千问 · 2021-1-27 06:56:28

背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的

千问 · 2021-1-27 06:56:28

先对原数组排序，然后用递归逐个向后选取里面的元素，以LZ的例子来说吧：
排序后intarr[]={5,4,3,1,1,1};选和为6
比如选取了5之后，这道题就成了在{4,3,1,1,1}里面选1了
选取了4之后，这道题就成了在{3,1,1,1}里面选2了
选取了3之后，这道题就成了在{1,1,1}里面选3了
用这样的方法递归，就能求出所有解，如果数组里面有重复的元素，解也会重复，可以用hash来判断一下是否存在该解，用来去掉重复

千问 · 2021-1-27 06:56:28

引用3楼haha_2005的回复:背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的
如果要随机的话，可以先随机产生几个元素，和需要小于6，然后再对不足部分用背包求解。且只需要返回第一组解！

千问 · 2021-1-27 06:56:28

引用5楼litaoye的回复:引用3楼haha_2005的回复:
背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的

如果要随机的话，可以先随机产生几个元素，和需要小于6，然后再对不足部分用背包求解。且只需要返回第一组解！
但是这样不一定能找到需要的结果啊。

千问 · 2021-1-27 06:56:28

引用6楼haha_2005的回复:引用5楼litaoye的回复:
引用3楼haha_2005的回复:
背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的

如果要随机的话，可以先随机产生几个元素，和需要小于6，然后再对不足部分用背包求解。且只需要返回第一组解！
但是这样不一定能找到需要的结果啊。
比如intarr[]={2,4,8};
和为7
则没有结果的

千问 · 2021-1-27 06:56:28

引用6楼haha_2005的回复:引用5楼litaoye的回复:
引用3楼haha_2005的回复:
背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的

如果要随机的话，可以先随机产生几个元素，和需要小于6，然后再对不足部分用背包求解。且只需要返回第一组解！
但是这样不一定能找到需要的结果啊。
比如intarr[]={2,4,8};
和为7
则没有结果的

千问 · 2021-1-27 06:56:28

引用3楼haha_2005的回复:背包问题是贪婪算法，这个问题好像不可以吧，这个问题是“随机”的
谁说0-1背包问题是贪婪算法呀
动态规划，回溯，分支限界都可以解决