A solver for the subset sum problem
- Dynamic programming
- Bellman
- Array
-a dynamic-programming-bellman-array - List (only optimal value)
-a dynamic-programming-bellman-list - Word RAM (only optimal value)
-a dynamic-programming-bellman-word-ram - Word RAM with recursive scheme
-a dynamic-programming-bellman-word-ram-rec
- Array
- Balancing
- Array (only optimal value)
-a dynamic-programming-balancing-array
- Array (only optimal value)
- Bellman
Compile:
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build --config Release --parallel cmake --install build --config Release --prefix installDownload data:
python3 scripts/download_data.pySolve:
./install/bin/subsetsumsolver --verbosity-level 1 --input data/pthree/pthree_1000_1 --algorithm dynamic-programming-bellman-word-ram-rec==================================== KnapsackSolver ==================================== Problem ------- Subset sum problem Instance -------- Number of items: 1000 Capacity: 250000 Algorithm --------- Dynamic programming - Bellman - word RAM - recursive scheme Parameters ---------- Time limit: inf Messages Verbosity level: 1 Standard output: 1 File path: # streams: 0 Logger Has logger: 0 Standard error: 0 File path: Time (s) Sol. Value Bound Gap Gap (%) Comment -------- ---- ----- ----- --- ------- ------- 0.000 1 0 250000 250000 100.00 0.033 1 250000 250000 0 0.00 algorithm end (solution) Final statistics ---------------- Value: 250000 Has solution: 1 Bound: 250000 Absolute optimality gap: 0 Relative optimality gap (%): 0 Time (s): 0.0330949 Solution -------- Number of items: 484 / 1000 (48.4%) Weight: 250000 / 250000 (100%) Feasible: 1 Run tests:
export SUBSET_SUM_DATA=$(pwd)/data cd build/test ctest --parallel