0 
def knapSack(A,L,R,K,N,Sum):
    if(K==0):
        if((L>=Sum)or(R<=Sum)):
            return 1
        else:
            return 0
    if((N==0)and(K!=0)):
        return 0
    else:
        return knapSack(A,L,R,K,N-1,Sum)+knapSack(A,L,R,K-1,N-1,Sum:=Sum+A[N-1])
A = [2,4,10,25]
K = 2
L = 3
R = 13
Sum=0
n = len(A)
print(knapSack(A,L,R,K,n,Sum))

这段代码的输出是： 4
解释：
25+10 =35
25+4 = 29
25+2 = 27
10+4 = 14
这些和满足给定条件 if((L>=Sum)or(R<=Sum )) 其中 L=3 R=13
K 是子集的大小。这里，K = 2
当 K = 3

A = [2,4,10,25]
K = 3
L = 3
R = 13
Sum = 0
n = len(A)
print(knapSack(A,L,R,K,n,Sum))

当 K = 3 时，此代码的输出为： 4
解释：
4+10+25 = 39
2+4+25 = 31
2+10+25 = 37
2+4+10 = 16
这些和满足给定条件 if( (L>=Sum)or(R<=Sum)) where L=3 R=13

有没有办法在动态规划或任何其他更好的方法中解决这个问题？

4

1 回答 1

0

这是您可以使用的动态编程算法。该算法将用于生成 size 的所有子集K。该算法使用一个接一个的元素A来构建子集。

脚步

  1. list用初始化empty seta 还要初始化 a global_counter，它将用于保持K满足给定条件的大小子集的计数。

  2. 迭代 的元素A。对于每个A[i]，请执行以下操作；

    一世。通过附加到中的所有当前元素来创建新的子集（注意当前包含使用创建的子集）。A[i]listlistA[0] to A[i-1]

    ii. 2.i对于在using中创建的每个新子集A[i]，设sum为子集中元素的总和， 为子集中count元素的数量。如果count == K AND (sum <= L OR sum >= R)然后增加global_counter. 如果count < K，则将新创建的子集插入list.

  3. 返回global_counter.

注意(sum, count)：我们将使用对来表示子集，而不是将每个中间子集存储为元素列表。其中sum表示子集中元素的总和，而count表示子集中元素的数量。通过这种方式，我们可以减少存储所有创建的子集所需的内存以及每次创建子集时计算sum和count所需的时间，因为sum新count创建的子集可以在恒定时间内从其先前的子集更新。

时间复杂度：O(2^N) - 请注意，在最坏的情况下，K = N

import java.util.ArrayList;
import java.util.List;

public class SubsetK {
    public static void main(String[] args) {
        int[] A = {2,4,10,25};
        int L = 3;
        int R = 13;

        int K = 3;
        System.out.println("K: "+K+", Result: "+countSubSets(A,K,L,R));
    }

    private static int countSubSets(int[] A, int K, int L, int R){
        //create array to hold subsets of size 0,1,...,(K-1)

        //since we are only interested in the sum of a subset, a subset will be
        //represented as (sum, count) pairs. Where sum is the sum of elements in the
        //subset, and count is the number of elements in the subset.
        
        List<int[]> dp = new ArrayList<>(); // list of [sum,count] pairs

        //initialize the array with the empty set
        dp.add(new int[]{0,0});

        int global_count = 0;
        for (int ele : A) {
            int size = dp.size();
            for (int j = 0; j < size; j++) {
                
                int sum = dp.get(j)[0] + ele;
                int count = dp.get(j)[1] + 1;

                //check if condition is satisfied
                if (count == K && (sum <= L || sum >= R))
                    global_count++;

                //we only store subsets of size 0,..,(K-1)
                //since they will be used to build bigger subsets
                if (count < K)
                    dp.add(new int[]{sum, count});
            }
        }
        return global_count;
    }
}
于 2022-01-12T19:10:34.127 回答