4

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...


1

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic. I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and ...


1

It is observed that, we can get the result by just reducing the values of chocolates and wrappers by 1 and then divide them to get the result (choc-1)/(wrap-1). First, we can verify by brute force that the number of additional chocolates we can get by returning wrappers repeatedly is indeed (choc-1)/(wrap-1). Second, here is how we can understand or prove ...


1

Here's an O(1) space, O(n) time algorithm with Java code. Logic: Let $P_i$ denote the price of the stock on day $i$. Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$. If you had sold before day $i$ you can buy again at day $i$. ...


Only top voted, non community-wiki answers of a minimum length are eligible