Available online at https://journal.
com/index.
php/ijqrm/index International Journal of Quantitative Research and Modeling e-ISSN 2721-477X p-ISSN 2722-5046 Vol.
No.
3, pp.
316-322, 2025
Implementation of Dynamic Programming Algorithm on The Integer Knapsack Problem .
(Case Study: J&T Cargo Agent Purwokert.
Leni Puspitasari1*.
Agus Sugandha2.
Siti Rahmah Nurshiami3
1,2,3
Department of Mathematics.
Faculty of Mathematics and Natural Sciences.
Universitas Jenderal Soedirman.
Indonesia *Corresponding author email: leni.
puspitasari@mhs.
Abstract The aim of this research is to solve the integer knapsack 0/1 problem, which is a problem of selecting goods from a large number of available goods where each item has a different weight and profit.
Shipping goods in the J&T Cargo Purwokerto shipping service is one of the many problems in selecting goods.
Shipping goods in J&T Cargo Purwokerto is carried out in stages with a higher profit value first because the shipping load capacity can only accommodate 700 kg.
In order for J&T Cargo Purwokerto agents to obtain maximum profits, the selection of goods to be shipped must be carried out first.
The selection of goods in J&T Cargo Purwokerto agents can be solved using the integer knapsack problem 0/1 method using the forward recursive dynamic programming algorithm with the help of Matlab R2021A software.
The results showed that on July 1, 2025, the maximum profit was obtained of IDR 3,038,850 with a weight of 700 kg.
On July 2, the maximum profit was obtained of IDR 4,884,985 with a weight of 700 kg.
On July 3, the maximum profit was obtained of IDR 7,732,155 with a weight of 699 kg.
Keywords: Integer Knapsack Problem 0/1.
Algorithm.
Dynamic Programming Algorithms Introduction Optimization is a common problem in everyday life.
Solving optimization problems is a way to determine optimal results within existing constraints.
Some optimization problems encountered in everyday life include determining public transportation routes, determining workforce size, and scheduling.
Another interesting optimization problem to discuss is the challenges faced by freight forwarding services.
Freight forwarding services are now commonplace and highly sought after to facilitate the delivery of goods, both long and short distances.
Shipping costs depend on the distance and weight of the goods.
To maximize profits with minimal costs and limited container capacity, the goods to be distributed must be carefully selected.
J&T CargoPurwokerto is one of the freight forwarding service providers that has ten type A outlets, namely outlets that receive and send packages from all over Indonesia and eleven type B outlets, namely outlets that only accept package pick-ups.
There are several services available at J&T Cargo Purwokerto, namely fast track with a minimum weight of 10 kg, mass track with a minimum weight of 100 kg, and FTL .
ull truck loa.
which is a fleet rental service such as cars, trucks, and others.
Shipping goods at J&T Cargo Purwokerto prioritizes longer distance locations, because they have large profits, for closer locations they will be sent the next day.
This is done because the available container capacity to accommodate goods is limited and not comparable to the number of goods to be shipped, so goods must be shipped in installments based on greater profits first to obtain maximum profits.
The problem of selecting shipping goods by J&T Cargo Purwokerto can be solved by solving the integer knapsack problem.
The knapsack problem or rucksack problem is a combinatorial optimization problem to find the best solution from many possible solutions (Martello & Toth, 1990.
Messac, 2.
The knapsack problem occurs when there are n items that cannot all be put into a storage area.
The available items have different weights and values.
The goal of solving the knapsack problem is to obtain maximum profit from the selection of available items without exceeding the storage capacity (Cormen et al.
, 2022.
Siang, 2.
There are four types of knapsack problems, namely the bounded knapsack problem which means that each item available is limited in number or there is only one unit of the item, the unbounded knapsack problem which means that each item available is unlimited in number or there is more than one unit available, the fractional knapsack problem which means that the number of items for each item can be fractional, and the integer knapsack problem .
which means that each item is only available in one unit.
This research will Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
use the integer knapsack problem .
because a value of 0 will be given to items that are not selected and sent the next day and a value of 1 will be given to items that are selected to be sent that day.
Literature Review Research on the knapsack problem has been conducted by Rois et al.
on solving integer knapsack problems using greedy, dynamic programming, brute force and genetic algorithms, from this study it can be concluded that the dynamic programming algorithm is an effective and efficient algorithm for solving integer knapsack problems for small and large scale data.
Research by Pitaloka .
on the 0-1 knapsack optimization problem using the dynamic programming algorithm concluded that dynamic programming solves problems by decomposing the solution into a set of steps or stages so that there is a series of related decisions.
Extensive research has been conducted on the knapsack problem.
A comparative study by Ezugwu et al.
analyzed heuristic algorithms for the 0/1 knapsack problem and compared their performance with the dynamic programming approach, showing the relative effectiveness of both methods.
Similarly.
Sharma & Kumar .
conducted a comparative study of dynamic programming and genetic algorithms for solving the knapsack problem, providing insights into which algorithm is more suitable under different conditions.
Furthermore.
Agrawal & Jain .
specifically discussed the implementation of a dynamic programming approach for the 0/1 knapsack problem.
Their work concluded that dynamic programming solves problems by decomposing the solution into a set of stages or a series of related decisions.
A survey by Dutta & Barman .
also reviewed various algorithms used for the 0/1 knapsack problem, including dynamic programming, and concluded that it is a robust choice for optimization problems where an optimal solution is required.
Based on these studies, it is clear that dynamic programming is an effective and efficient algorithm for solving the integer knapsack problem .
for both small and large-scale data.
Therefore, this research is interested in discussing and continuing this line of inquiry with different data, using the dynamic programming algorithm with a case study at J&T Cargo Purwokerto, to enable the company to select the goods for shipment to obtain maximum profit.
Another study conducted by Research by Salsabila .
on the application of the greedy algorithm and the dynamic programming algorithm to the integer knapsack problem, concluded that the dynamic programming algorithm is more optimal than the greedy algorithm based on the maximum profit obtained.
Therefore, researchers are interested in discussing and continuing the study by Salsabila .
on integer knapsack .
with different data and using the dynamic programming algorithm.
With the case study of J&T Cargo Purwokerto using the forward recursive dynamic programming algorithm so that J&T Cargo Purwokerto can select the goods to be sent first so as to obtain maximum profit.
Methods The methods used in this research are literature review and case study.
Literature review involves reading, studying, understanding, and analyzing materials from literature or other references such as books, theses, journals, and e-books.
The case study was conducted at J&T Cargo Purwokerto.
The data used in this research is secondary data in the form of data on shipping destinations, weight, and profit data obtained from J&T Cargo Purwokerto.
The steps taken in this research are as follows:
Data collection, .
determine the problem structure by defining all the variables obtained, .
solve problems using dynamic programming algorithms, .
compile a table of completion of each stage and capacity , .
make decisions by choosing the maximum benefit at each stage.
Results and Discussion Goods Delivery Data Data obtained from the J&T Cargo Purwokerto agent in the form of data on the weight of goods, goods profit, shipping destination, and the maximum capacity of the shipping load in the form of a Grand Max car with a maximum capacity of 700 kg to accommodate goods that will be sent to the Sokaraja branch on July 1, 2025 to July 3, 2025.
The data is then processed using Matlab R2021A to find out which goods will be sent first, by giving a value of 1 to the goods to be sent and giving a value of 0 to the goods that will be sent the next day.
Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
Table 1: Data on goods received on July 1, 2025
Item number Shipping Destination Weight of Goods Profit Goods Gunungkidul Regency IDR 41,655 Bogor Regency IDR 47,320 Tangerang Regency IDR 47,320 Bandung
IDR 58,500
Cilacap Regency IDR 73,500 Bekasi City IDR 47,320 Serang City IDR 153,000 Lamongan Regency IDR 50,000 South Jakarta
IDR 40,500
Sleman Regency IDR 63,000 Surakarta City IDR 35,000 East Jakarta
IDR 62,000
Kuningan Regency IDR 40,500 Semarang City IDR 35,000 Denpasar City IDR 71,000 Gresik Regency IDR 250,000 Surabaya City IDR 197,000 Central Jakarta
IDR 75,000
Tangerang Regency IDR 46,000 Karanganyar Regency IDR 55,000 Surakarta City IDR 65,000 Blitar Regency IDR 46,000 Batang Regency IDR 176,500 Bontang City IDR 317,000 Semarang City IDR 35,000 Bogor Regency IDR 165,000 Sleman Regency IDR 39,080 Bintan Regency IDR 379,000 Kebumen Regency IDR 41,655 West Jakarta
IDR 40,500
West Bandung Regency IDR 92,500 Pekalongan Regency IDR 85,500 Central Jakarta
IDR 40,500
North Jakarta
IDR 124,000
Based on the data in Table 1, there are 34 items with a total weight of 727 kg and a total profit of IDR 3,135,850, with a maximum shipping load capacity of( )to the Sokaraja branch office, weighing 700 kg.
Because the total weight of the goods exceeds the maximum shipping capacity, it is necessary to select which goods will be shipped to the Sokaraja branch office on July 1, 2025.
Integer Model Knapsack Problem .
The steps in forming an integer knapsack problem model include:
Identify the data variables in Table 4.
1 by notating the goods as , the weight of the item as , and the profit of the item as .
Forming an integer model of the knapsack problem .
Determine the objective function Determine the constraint function Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
Determining decision variables : Decision whether the item is taken .
or not .
, .
Solve the integer knapsack problem .
with the dynamic programming algorithm.
Methods Based on Table 1, the stages for solving integer knapsack .
using the dynamic programming algorithm are as .
Determining the problem structure .
Using the forward recursive equation, namely:
( )
( )
( )
( )
Maximum profit at the stage with capacity Knapsack capacity at stageProfit object toWeight of the object .
Prepare a settlement table at the 6th stage with capacity , for and .
Determine decisions by choosing optimal profits at each stage that has been carried out.
Figure 1: Matlab R2021A output of calculation results using dynamic programming Based on Figure 1, it is obtained the solution of the integer knapsack problem .
with the dynamic programming algorithm using Matlab R2021A software resulted in a total weight of goods included in the shipping load of 700 kg with a profit of IDR 3,038,850.
The goods that will be included in the shipping load on July 1, 2025 are items 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34.
The 11th and 12th items will be included in the shipping load the next day.
Next Day Item Selection .
Selection of items to be shipped on July 2, 2025 Items to be shipped on July 2, 2025 consist of items that were not shipped on July 1, 2025 and items that were newly received on July 2, 2025 that will be selected for shipping.
On July 2, 2025, there were 44 items with a total weight of 723 kg and a total profit of IDR 4,931,900, with a maximum shipping load capacity of ( ) to the Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
Sokaraja branch office amounting to 700 kg and the selection of incoming goods delivery on July 2, 2025 will be carried out by reducing the maximum capacity of the delivery load with the total weight of the goods on July 1, 2025 that cannot be sent, namely 27 kg, so that the maximum delivery load capacity is 673 kg.
With the objective function:
and the constraint function:
Figure 2: Matlab R2021A output of selection of items shipped on July 2, 2025 Based on Figure 2, the items that will be included in the shipping load are items 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 44 with a profit of IDR 4,787,985.
The total weight of the goods to be shipped on July 2, 2025 was 700 kg and the total profit obtained was IDR 4,884,985, where 27 kg was the weight of the goods that could not be shipped on July 1, 2025 with a profit of IDR 97,000 and 673 kg was the weight of the goods selected to be shipped on July 2, 2025.
Selection of items to be shipped on July 3, 2025 Items to be shipped on July 3, 2025 consist of items that were not shipped on July 2, 2025 and items that were newly received on July 3, 2025 that will be selected for shipping.
There are 73 new items that have just arrived with a total weight of 2041 kg and a total profit of IDR 13,017,575, with a maximum shipping load capacity of( )to the Sokaraja branch office amounting to 700 kg and the selection of incoming goods delivery on July 3, 2025 will be carried out by reducing the maximum capacity of the delivery load with the total weight of the goods on July 2, 2025 that cannot be sent, namely 50 kg, so that the maximum delivery load capacity is 650 kg.
Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
Figure 3: Matlab R2021A output of selection of items shipped on July 3, 2025 Based on Figure 3, the items that will be included in the shipping loadnamely items 3, 5, 6, 11, 13, 15, 23, 24, 37, 45, 46, 50, 51, 52, 58, 60, 61, 68, 69 with a maximum profit of IDR 7,588,240 and a maximum weight of 649 kg.
The total weight of the goods transported on July 3, 2025, was 699 kg.
and the total profit obtained was IDR 7,732,155 where 50 kg was the weight of the goods that could not be sent on July 2, 2025 with a profit of IDR 143,915 and 649 kg was the weight of the goods selected to be sent on July 3, 2025.
Conclusion Conclusion Based on the research that has been conducted, the following conclusions were obtained.
The optimization model obtained for the integer knapsack problem 0/1 using this dynamic programming algorithm is as follows:
( )
( )
( )
By stating the number of items and stating the load capacity, it can be concluded:
On July 1, 2025, 34 items were imported with a loading capacity of 700 kg.
On July 2, 2025, 44 items were shipped, and the loading capacity was 673 kg.
On July 3, 2025, there were 73 items entered, and the loading capacity was 650 kg.
In the J&T Cargo Purwokerto case study data from July 1-3, the results of solving the integer knapsack problem 0/1 using dynamic programming were obtained as follows:
On July 1, 2025, after calculations were carried out using the dynamic programming algorithm, 32 items were obtained to be transported on that day with a maximum weight of 700 kg and a maximum profit of IDR 3,038,850.
On July 2, 2025, after calculations were carried out using the dynamic programming algorithm, a total of 43 items were obtained that would be transported on that day with a maximum weight of 700 kg and a maximum profit of IDR 4,884,985.
Puspitasari et al.
/ International Journal of Quantitative Research and Modeling.
Vol.
No.
3, pp.
316-322, 2025
On July 3, 2025, after calculations were carried out using the dynamic programming algorithm, a total of 22 items were obtained that would be transported on that day with a maximum weight of 699 kg and a maximum profit of IDR 7,732,155.
Suggestion For further research, it can be developed by using other variables such as the volume variable of goods so that it does not only use the weight and profit variables of goods.
It can also use the backward recursive dynamic programming algorithm or use other algorithms that can solve the integer knapsack problem.
Furthermore, it can also be developed by using different knapsack problems such as bounded knapsack or fractional knapsack to adjust the problem to the existing reality.
References