0

私はこの質問に興味を持っています。

セットP={1、2、3、.. n}からサブセットを選択する方法はいくつありますか？サブセットSは、次の条件を満たす必要があります。

x（x∈P、xは集合Pの要素）を選択してSを作成する場合、Sにa*xおよびb*xを選択することはできません。

制約：

1 <= n <= 1000
2 <= a < b <= n
b % a != 0 ( b is not divisible by a)

例 ：

n = 3 , a = 2, b = 3
so total subsets are 5 ,i.e, {}, {1}, {2}, {3}, {2, 3} 
as if in a particular subset there is 1 so 1*2 = 2 and 1*3 cant be there.
so {1,2}, {1,3} and {1,2,3} can't be there
4

2 に答える 2

1

更新しました

これは、整数シーケンスのオンライン エンサイクロペディアである OEIS のシーケンス A051026 : {1, 2, ..., n} のプリミティブ サブシーケンスの数に関連しています。

項を計算する簡単な方法はないと思います。nが素数の場合を除いて、再帰的な計算でさえ自明ではありません。

a(n) = 2 * a(n-1) - 1

ここでの問題と "A051026" の両方が、上記のシーケンスの一般化のサブ問題と考えることができます。「A051026」は、(a,b,..) = (2,3,4,5...)「all the integers >= 2」などのインスタンスです。

于 2013-03-16T23:12:04.377 に答える
0

私は、許可されていないS の部分集合の数である補数を計算する方が簡単だと思います。これは、 を割るようなSペアが少なくとも 1 つ存在する場合のサブセットの数です。その数 M' を計算したら、それを S の部分集合の総数 2 nから差し引くだけです。(a,b)ab

S許可されていないサブセットの数を計算するには、包含と除外の原則を適用する必要があります。ソリューションの実装は簡単ではありませんが、別のアプローチはないと思います。

于 2013-03-16T22:36:22.767 に答える