|
|
EXAMPLE
|
The sequence of spanning product-sum knapsack partitions begins
0: ()
1: (1)
2: (2) (1,1)
3: (3) (2,1) (1,1,1)
4: (4) (3,1)
5: (5) (4,1) (3,2) (3,1,1)
6: (6) (5,1) (4,2) (4,1,1) (3,3)
7: (7) (6,1) (5,2) (5,1,1) (4,3) (4,2,1) (4,1,1,1) (3,3,1)
8: (8) (7,1) (6,2) (6,1,1) (5,3) (5,2,1) (5,1,1,1) (4,4) (4,3,1) (3,3,2)
9: (9) (8,1) (7,2) (7,1,1) (6,3) (6,2,1) (6,1,1,1) (5,4) (5,3,1) (4,4,1) (4,3,2) (3,3,3)
A complete list of all products of sums covering the parts of (4,1,1,1) is:
(1+1+1+4) = 7
(1)*(1+1+4) = 6
(4)*(1+1+1) = 12
(1+1)*(1+4) = 10
(1)*(1)*(1+4) = 5
(1)*(4)*(1+1) = 8
(1)*(1)*(1)*(4) = 4
These are all distinct, so (4,1,1,1) is a spanning product-sum knapsack partition of 7.
A complete list of all products of sums covering the parts of (5,3,1,1) is:
(1+1+3+5) = 10
(1)*(1+3+5) = 9
(3)*(1+1+5) = 21
(5)*(1+1+3) = 25
(1+1)*(3+5) = 16
(1+3)*(1+5) = 24
(1)*(1)*(3+5) = 8
(1)*(3)*(1+5) = 18
(1)*(5)*(1+3) = 20
(3)*(5)*(1+1) = 30
(1)*(1)*(3)*(5) = 15
These are all distinct, so (5,3,1,1) is a spanning product-sum knapsack partition of 10.
An example of a spanning sum-product knapsack partition that is not a spanning product-sum knapsack partition is (5,4,3,2).
|
|
|
MATHEMATICA
|
sps[{}]:={{}};
sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
rsuks[n_]:=Select[IntegerPartitions[n], Function[q, UnsameQ@@Apply[Times, Apply[Plus, mps[q], {2}], {1}]]];
Table[Length[rsuks[n]], {n, 10}]
|
