Montecarlo Approach For Solving Unbound Knapsack Problem

In many real-world problems, random variables influence the outcome of a decision-making process. All those variables and their potential interactions are typically difficult to consider. Under such uncertainty, AI methods are useful tools for generalizing past experiences to produce solutions to the previously unseen instances of the issue. Unbound Knapsack Problems (UKP) are important research topics in many fields like portfolio and asset selection, selection of minimum raw materials to reduce the waste and generating keys for cryptosystems. Given the uncertainty in data, capacity and time constraint, decision-makers have to look at the possible combination of data with maximum return considering both short term and long term returns. This paper applies Monte Carlo Tree Search (MCTS) to solve UKP by selecting the best items for the given knapsack capacity and the modified Upper Confidence Bound (UCB) algorithm for calculating the Cumulative Rewards (CR). We have shown the results of cumulative rewards by increasing the iterations. The experiment result presents not a single solution but a set of optimal solutions. The execution time of MCTS is measured by varying the number of available items. The measurement result shows the improvement in execution time as the number of items increases.