给定一组有限的实数实数，可产生所有总和< = k的子集 [英] Given a finite set of sorted real numbers produce all possible subsets whose sum <= k

问题描述

我想知道是否存在解决此问题的算法.它有点类似于背包0-1问题或电源设置问题，但有所不同.

I would like to know if there exist algorithms that solves this issue. It is little bit similar to knapsack 0-1 problem, or power set problem however it is different.

给定有限的一组排序的实数，我们需要生成总和<= k的所有可能的子集.在这里k是实数，排序后的实数都是正数.例如，一个数组= {1.48，2.21 3.07，4.35，4.46}，k = 5.94输出为:{4.46}，{4.46、1.48}，{4.35}，{4.35、1.48}，{3.07}，{3.07、2.21}，{2.21}，{2,21、1.48}和{1.48}.

Given a finite set of sorted real numbers we need to generate all possible subsets whose sum <= k. Here k is real, the sorted real numbers are all positive. For example an array = {1.48, 2.21 3.07, 4.35, 4.46} and k = 5.94 Output is : {4.46}, {4.46, 1.48}, {4.35}, {4.35, 1.48}, {3.07}, {3.07, 2.21}, {2.21}, {2,21, 1.48} and {1.48} .

一种解决方法是简单地从最高数字{4.46}遍历，以查看您可以在购物篮中包含多少，然后继续进行下一个最低数字{4.35}，依此类推.有没有一种有效的方法可以做到这一点?让我知道

One way to solve is to simply traverse from highest number {4.46} to see how many you can inlude in the basket then continue going next lowest number {4.35} and so on. Is there an efficient way to do this? let me know

推荐答案

贪婪算法肯定可以工作.为了利用对输入进行排序的事实，可以使用二进制搜索.

Greedy algorithm can definitely work. To take advantage of the fact that the input is sorted, binary search can be used.

基本思想是:首先通过二进制搜索在小于K的数组中搜索最大数，将结果元素推入堆栈，然后递归搜索在该元素结尾的子数组求和K-该元素的值.完成此操作后，在子数组中搜索总和K，以涵盖未选择该元素的情况.

The basic idea is: first search for the biggest number in the array that is smaller than K by binary search, push the result element to a stack, then recursively search the subarray that ends at that element for a sum K - the value of that element. After this is done, search in the subarray for a sum K to cover the situations in which that element is not chosen.

示例代码:

void boundedSumSubarray(float * arr, int size, float K, stack S) {
    int pos=binarySearch(arr,size,K);
    if (pos>=0) {
        pushStack(S,arr[pos]);
        boundedSumSubarray(arr,pos-1,K-arr[pos],S);
        popStack(S);
        boundedSumSubarray(arr,pos-1,K,S);
    } else
        printStack(S);
}

这篇关于给定一组有限的实数实数，可产生所有总和&lt; = k的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！