## 3 Proposed Method
### System Model  
Our work proposes state, action, and reward in MDP for solving an MKP by referring to and modifying parts of the existing work [11]. The state transition is deterministic here and the next state is decided by the current state and action. State: The proposed state has profit and weight information on at most \(N\) items to be selected, and the capacity information of all knapsacks. Figure 1 shows the proposed states of MKP. Let \(|I|\) denote the number of items to be selected. Then, it indicates the number of problems for the agent to solve by selecting a single item at each time. Let \(c_{j}\) denote the \(j\)-th largest capacity in the state. Each of the knapsack problems has a different target number, which is the number of not-fully-occupied knapsacks that can take more items. Because the target number of the knapsack is single, [PERSON] et al. [11] use one capacity field, whereas our method can use one or more capacity fields because we target not only a single knapsack but also multiple knapsacks. In Figure 1, it is assumed \(M\) is equal to the number of the knapsack. There are \(M\) capacity fields, which correspond to \(c_{1}\), \(c_{2}\), \(c_{3}\), \(\cdots\), \(c_{M}\) and are sorted in descending order of the capacity size. At the first, \(c_{1}\) with the largest size of the capacity is located, at the second, \(c_{2}\) with the second largest size of the capacity is located, and at the last, \(c_{M}\) with the smallest size of capacity is located. In Figure 1, \(\sum_{i}p_{i}\) and \(\sum_{i}w_{i}\) are the summed profit of items and the summed weight of items, respectively. In the following, profits and weights information on the items are listed. Here, \(pn_{i}\) is a normalized \(p_{i}\) as shown in (4). \[pn_{i}=\frac{p_{i}}{p_{\max}}, \tag{4}\]  
where \(p_{i}\) is divided by \(p_{\max}\), which is the maximum size of the given profits. The pairs of \(pn_{i}\) and \(w_{i}/c_{1}\) are listed in descending order of \(\frac{p_{i}}{w_{i}}\) value (\(i\in I\)). In the fields of each item, \(pn_{i}\) is located at the first, and \(\frac{w_{i}}{c_{1}}\) is located at the second. As a result, \(pn_{1}\) is located at the first, and \(\frac{w_{1}}{c_{1}}\) is located at the second. On the third, \(pn_{2}\) is located, and on the fourth \(\frac{w_{2}}{c_{1}}\) is located. The left items are listed in the same way. If an item is selected for a certain knapsack or discarded, the state does not have the item's information anymore. The left \((N-|I|)\times 2\) fields have zero values. Action: In action space, there are \(N\) actions \(A=\{1,...,N\}\). An action \(a\in A\) implies that the \(a\)-th item in item set \(I\) is selected and is put into the knapsack that has a maximum capacity \(c_{1}\). Note that the size of action space is fixed to \(N\) regardless of the number of knapsacks. Reward functions: If the agent's action successfully allocates the item to the knapsack, the environment returns a positive reward. When the item's weight exceeds the capacity of the target knapsack, a negative reward is given. When the chosen action is greater than the number of remaining items and an already chosen item is chosen, a fatal negative reward is given compared to the previous negative case. The proposed reward value is given by  
\[r_{t}= \begin{cases}pn_{i},&w_{i}\leq c_{j}\\ -\eta,&w_{i}>c_{j}\\ -\xi,&a\geq|I|.\end{cases}  \tag{5}\]  
Our reward value is different from that in [11], which is given by  
\[\hat{r}_{t}= \begin{cases}\frac{p_{i}}{w_{i}c},&w_{i}\leq c\\ -\frac{w_{i}}{c},&w_{i}>c\\ -c,&a\geq|I|.\end{cases}  \tag{6}\]  
In the first case, the reward is set to \(pn_{i}\) without considering the effect of weight and capacity so that the objective is closer to the MKP's objective function in (1). In the second reward case of -\(\eta\), we remove the effect of the weight of the violated item on the reward because the only thing the agent needs to know is whether the weight exceeds the capacity or not.