Repository navigation
ADD BITWISE DP / SOS DP #7503
Description
Activity
Hello, I would like to work on this issue. I can add a clean, well-documented Java implementation of the Traveling Salesperson Problem (TSP) using Bitmask DP, along with the necessary JUnit tests.
I have put together a Java implementation for the Traveling Salesperson Problem (TSP) using Bitmask DP, along with the necessary documentation.
Hi @priyanka-hotkar,
Can you please look once I was trying to complete this issue and if you any doubt, please let me know!
#7517Hi, @priyanka-hotkar can you please check once this pr #7517.
if any issue still face i try to fix it.Hi @priyanka-hotkar, Can you please look once I was trying to complete this issue and if you any doubt, please let me know! #7517
Hi,
I am not the maintainer of the repository, can you please tag one of them ?Reacted by Narendrakumar KumawatThis issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!
Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!
What would you like to Propose?
Add implementation(s) of dynamic programming on bitmasks, where DP state includes a bitmask representing a subset of elements already used/visited (e.g. dp[mask][i]). Useful for problems like TSP, optimal assignment, and subset-based counting where n is small (≤ ~20) and the order/combination of included elements matters. Covers core bit tricks (set/check/clear bit, iterate submasks) along with example problems.
Issue details
Bitmask DP represents a subset of elements as bits in an integer, where bit i being 1 means element i is included. The DP state dp[mask] (or dp[mask][i]) stores the best result for that subset, and transitions move from one mask to another by adding an element via mask | (1 << i). It's used when problems involve small sets (n ≤ ~20) and require tracking exactly which elements have been chosen, e.g., TSP, optimal assignment, and subset partitioning.
Additional Information
No response