4
$\begingroup$

I have five values ​​that I would like to add them so that they can be equal to or less than 3000.

v1 = 140; v2 = 280; v3 = 420; v4 = 560; v5 = 700; goal = 3000;
Subsets [{v1, v2, v3, v4, v5}]

For example:

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v2

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v3

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v4

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v5

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v2 + v2

-> 2940

v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v1 + v2 + v2 + v2

-> 2940

All are possibilities, among other possibilities.

Is there a feature that validates these possibilities?

$\endgroup$
7
$\begingroup$

Append 1 to the list of vs and use FrobeniusSolve:

w = {v1, v2, v3, v4, v5, 1};
res = FrobeniusSolve[w, 3000][[2;;, ;; 5]];
Length[res]

1345

Short @ res

{{0,0,0,0,1},{0,0,0,0,2},{0,0,0,0,3},{0,0,0,0,4},{0,0,0,1,0},<<1336>>,{19,0,0,0,0},{19,1,0,0,0},{20,0,0,0,0},{21,0,0,0,0}}

And @@ Thread[Total /@ res <= 3000]

True

Up to ordering, res is the same as Henrik's resulttable:

Sort[res] == Sort[resulttable]

True

An alternative way to use IntegerPartitions using w:

res2 = DeleteCases[Rest@IntegerPartitions[3000, All, w], 1, 2];
Length@res2

1345

restab = Map[Lookup[Counts[#], Most @ w, 0] &] @ res2;
Sort[res] == Sort[restab]

True

To get the totals that can be obtained using vs:

Sort[DeleteDuplicates[res.Most[w]]] (* or *)
Sort[3000 - DeleteDuplicates@Rest[FrobeniusSolve[w, 3000]][[All, -1]]]

{140, 280, 420, 560, 700, 840, 980, 1120, 1260, 1400, 1540, 1680, 1820, 1960, 2100, 2240, 2380, 2520, 2660, 2800, 2940}

Sort @ Counts[res.Most[w]]

<|140 -> 1, 280 -> 2, 420 -> 3, 560 -> 5, 700 -> 7, 840 -> 10, 980 -> 13, 1120 -> 18, 1260 -> 23, 1400 -> 30, 1540 -> 37, 1680 -> 47, 1820 -> 57, 1960 -> 70, 2100 -> 84, 2240 -> 101, 2380 -> 119, 2520 -> 141, 2660 -> 164, 2800 -> 192, 2940 -> 221|>

Update: You can also use Reduce and Solve:

v = {v1, v2, v3, v4, v5};
xv = Array[x, 5];
resReduce = Reduce[{v.xv <= 3000, ##&@@Thread[xv >= 0]}, xv, Integers][[2;;, All, -1]] /.
  {And | Or -> List}; 
resSolve = xv /. Rest@Solve[{v.xv <= 3000, ## & @@ Thread[xv >= 0]}, xv, Integers];
res == resReduce == resSolve

True

$\endgroup$
4
$\begingroup$
a = {140, 280, 420, 560, 700};
results = Join @@ DeleteCases[
     IntegerPartitions[#, {1, ∞}, a] & /@ Range[3000],
     {}
     ];
And @@ Thread[Total /@ results <= 3000]
resulttable = Map[Lookup[Counts[#], a, 0] &, results];
resulttable // Short

True

{{1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, <<1341>> , {19, 1, 0, 0, 0}, {21, 0, 0, 0, 0}}

$\endgroup$
3
$\begingroup$
v1 = 140; v2 = 280; v3 = 420; v4 = 560; v5 = 700; goal = 3000;
Select[Subsets[{v1, v2, v3, v4, v5}], Total[#] <= goal &]

Are you sure your "goal" is 3000? Every subset totals less than that.

And what does 21 * v1 in your question refer to? What is $21$, and why multiplication?

$\endgroup$
3
$\begingroup$
a = {140, 280, 420, 560, 700};
coef = Tuples[Range[0, 21], 5];
vec = coef.a;

Extract[coef, Position[Ramp[vec - 3000], 0]] // Short

{{0,0,0,0,0},{0,0,0,0,1},{0,0,0,0,2},{0,0,0,0,3},{0,0,0,0,4},{0,0,0,1,0},<<1335>>,{18,1,0,0,0},{19,0,0,0,0},{19,1,0,0,0},{20,0,0,0,0},{21,0,0,0,0}}

Pick[vec, Ramp[vec - 3000], 0] // Short

{0,700,1400,2100,2800,560,1260,1960,2660,1120,1820,2520,1680,2380,<<1318>>,2940,2800,2380,2940,2800,2660,2940,2520,2940,2800,2660,2940,2800,2940}

$\endgroup$
2
$\begingroup$

Could use integer linear programming via Maximize, for example. The constraint I use is overkill, all we really need to enforce is that values be nonnegative.

vals = {140, 280, 420, 560, 700};
goal = 3000;
vars = Array[v, Length[vals]];
Maximize[{vars.vals, 
  Flatten[{vars.vals <= goal, 
    MapIndexed[0 <= # <= Floor[goal/vals[[#2[[1]]]]] &, 
     vars]}]}, vars, Integers]

(* Out[1287]= {2940, {v[1] -> 10, v[2] -> 4, v[3] -> 1,
    v[4] -> 0, v[5] -> 0}} *)
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.