Home Online Manual
Top
Back: find_index
Forward: subset_sum02
FastBack:
FastForward:
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.2.43 subset_sum01

Procedure from library crypto.lib (see crypto_lib).

Usage:
subset_sum01(knapsack,solution)

Return:
binary list of the positions of the elements included in the subset sum or 0 if no solution exists

Note:
This will return the first solution of the ssk-problem, given be the smallest binary encoding. It wont return several solutions if they exist

Example:
 
LIB "crypto.lib";
list h=1,4,7,32;
subset_sum01(h,20);
==> 0
subset_sum01(h,11);
==> [1]:
==>    0
==> [2]:
==>    1
==> [3]:
==>    1
==> [4]:
==>    0
subset_sum01(h,33);
==> [1]:
==>    1
==> [2]:
==>    0
==> [3]:
==>    0
==> [4]:
==>    1