ABSTRACT (original article): Dynamic programming (DP) is a powerful algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. This paper presents an implementation of DP algorithms for two classic optimization problems: the Knapsack problem and the Traveling Salesman Problem (TSP). The solutions are developed and demonstrated using the Mathematica® programming language. For the Knapsack problem, we present two variants: with and without item repetition. The paper describes the mathematical formulation of each variant and provides detailed Mathematica code for their implementation. Examples are given to illustrate the effectiveness of the algorithms in finding optimal solutions. The TSP implementation demonstrates how DP can be applied to find the shortest Hamiltonian contour in a given network. The paper outlines the mathematical model, recurrent formula, and step-by-step solution process. An example with a four-node network is provided to showcase the algorithm’s application. This work highlights the versatility of dynamic programming in solving complex optimization problems and demonstrates the effectiveness of Mathematica as a tool for implementing and visualizing these solutions. The presented algorithms and code snippets serve as valuable resources for researchers and practitioners working on similar optimization challenges. CITATION (original article): Predrag S. Stanimirović and Artem Stupin, Dynamic programming in package Mathematica, ITM Web Conf., 72 (2025) 01001. https://doi.org/10.1051/itmconf/20257201001
Dynamic programming (DP) algorithms are often used for solving optimization problems. The Knapsack Problem is a classic optimization problem . It considers a set of items, each with a weight and a value, the goal is to determine the number of each item to include in a collection such that the total weight is as large as possible and less than or equal to a given capacity of the knapsack.
There are several variations of the Knapsack ProblemČ
1
.0/1 Knapsack Problem: an arbitrary item can be either taken or leaved.
2
.Unbounded Knapsack Problem: unlimited number of each item is available.
3
.Fractional Knapsack Problem: it is possible to take fractions of an item, meaning you can take any portion of it. This variant is solvable by a greedy algorithm.
In this notebook we solve the Knapsack problem using DP. Implementation of these solutions is developed in the programming language Mathematica.
Unbounded Knapsack problem
Unbounded Knapsack problem
There are n types of items, and there is an infinite supply of each type. For each item type, we know its weight, represented as weights[i] and the price, represented as values[i]. There is a backpack that can carry a maximum weight of T. The objective is to fill the backpack with items so that the total value of the items in the backpack is maximized. What is the maximum value that can be obtained?
n represents number of objects,
weights is the list list of weights of individual objects,
values is the list of values of individual objects,
T1 is the capacity of the knapsack
weights is the list list of weights of individual objects,
values is the list of values of individual objects,
T1 is the capacity of the knapsack
Let a[i] represent the optimal solution for the backpack of payload capacity i. include at least one object of type j, it indicates that weights[j] ≤ i, and the other objects must not exceed the carrying capacity of i - weights[j]. That part of the backpack will also be optimally filled (because the overall capacity backpack must be optimally filled), so
a[i]=a[i-weights[i]]+values[j].
Since we do not know which objects are optimal for a[i], we will try each object and then select the maximum value. The recursive formula is given by:
a[i]=max_{1<=i<=n,weights[j]<=i } {a[i],a[i-weights[j]]+values[j]}.
Each element p[i] in the list p keeps track of the index j of the object that provides the optimal value for the capacity i.
a[i]=a[i-weights[i]]+values[j].
Since we do not know which objects are optimal for a[i], we will try each object and then select the maximum value. The recursive formula is given by:
a[i]=max_{1<=i<=n,weights[j]<=i } {a[i],a[i-weights[j]]+values[j]}.
Each element p[i] in the list p keeps track of the index j of the object that provides the optimal value for the capacity i.
Knapsack[n_,weights_,values_,T1_]:=Module[{a={},p={},solution={},price=0,T=T1},For[i=1,i≤T+1,i++,AppendTo[a,0];AppendTo[p,-1]];For[i=1,i≤T+1,i++,For[j=1,j≤n,j++,If[weights[[j]]≤i,If[a[[i]]<a[[i-weights[[j]]]]+values[[j]],a[[i]]=a[[i-weights[[j]]]]+values[[j]];p[[i]]=j;]]]];T++;While[p[[T]]≥0,AppendTo[solution,p[[T]]];price+=values[[p[[T]]]];T-=weights[[p[[T]]]];];Print["Selected objects: ",solution];Print["Optimal value: ",price]];
0/1 Knapsack problem
0/1 Knapsack problem
Let a[c][i] represent the optimal solution for a knapsack of capacity c, where only the first i items are used. We introduced the second dimension to address the additional criterion that only one sample of each type can be included. This approach is more efficient than sequentially checking all items each time.
When we consider including item i in the filling of the knapsack, we have two choices: either include it or leave it. Our goal is to fill the knapsack optimally. If we decide to include the ith item in in the knapsack with capacity c, then the following equation applies:
a[c][i]=a[c-weights[i-1]][i-1]+values[i-1]
This equation represents the optimal filling for the knapsack of capacity c-weights[i-1], plus the value of the (i-1)th item.
If we did not take the (i-1)th item, then a[c][i] remains unchanged. This means we can proceed with the first i-1 items.
When we consider including item i in the filling of the knapsack, we have two choices: either include it or leave it. Our goal is to fill the knapsack optimally. If we decide to include the ith item in in the knapsack with capacity c, then the following equation applies:
a[c][i]=a[c-weights[i-1]][i-1]+values[i-1]
This equation represents the optimal filling for the knapsack of capacity c-weights[i-1], plus the value of the (i-1)th item.
If we did not take the (i-1)th item, then a[c][i] remains unchanged. This means we can proceed with the first i-1 items.
Knapsack1[n_,weights_,values_,T1_]:=Module[{a={},p={},solution={},price=0,T=T1},a=Table[0,{i,T+1},{j,n+1}];p=Table[-1,{i,T+1},{j,n+1}];For[i=2,i≤n+1,i++,For[c=1,c≤T+1,c++,a[[c,i]]=a[[c,i-1]];p[[c,i]]=p[[c,i-1]];If[weights[[i-1]]<c,If[a[[c,i]]≤a[[c-weights[[i-1]],i-1]]+values[[i-1]],a[[c,i]]=a[[c-weights[[i-1]],i-1]]+values[[i-1]];p[[c,i]]=i-1]]]];i=n+1;T=T+1;While[p[[T,i]]≥0&&i>0,AppendTo[solution,p[[T,i]]];price+=values[[p[[T,i]]]];i=p[[T,i]];T-=weights[[i]];];Print["Selected objects: ",solution];Print["Optimal value: ",price];];
Mathematica includes standard function KnapsackSolve
Mathematica includes standard function KnapsackSolve
?KnapsackSolve
KnapsackSolve[{,,…},maxtotalcost] solves the knapsack problem of finding the maximum number of items associated with each of the , subject to the constraint that the total cost is not larger than maxtotalcost.KnapsackSolve[{{,},{,},…},maxtotalcost] finds a number of items that maximizes the total payoff, while satisfying the constraint on the total cost.KnapsackSolve[{{,,},…},maxtotalcost] allows at most copies of item i.KnapsackSolve[items,{maxtotalpayoff,maxtotalcost}] finds a result that gives a total payoff not larger than maxtotalpayoff.KnapsackSolve[items,{maxtotalpayoff,maxtotalcost,maxtotalcount}] adds the constraint of having no more than maxtotalcount items in total. KnapsackSolve[,…,maxtotals] labels each type of item and gives the result as an association.
cost
1
cost
2
cost
i
payoff
1
cost
1
payoff
2
cost
2
payoff
1
cost
1
maxcount
1
maxcount
i
label
1
itemspec
1
Examples
Examples
Example 1
Example 1
n=3;weights={10,45,20};values={45,120,100};T=50;
Knapsack[n,weights,values,T]
Selected objects: {1,3,3}
Optimal value: 245
KnapsackSolve[{{45,10},{120,45},{100,20}},50]
{1,0,2}
Knapsack1[n,weights,values,T]
Selected objects: {3,1}
Optimal value: 145
KnapsackSolve[{{45,10,1},{120,45,1},{100,20,1}},50]
{1,0,1}
Example 2
Example 2
n=4;weights={6,3,4,2};values={30,14,16,9};T=10
10
Knapsack[n,weights,values,T]
Selected objects: {1,4,4}
Optimal value: 48
KnapsackSolve[{{30,6},{14,3},{16,4},{9,2}},10]
{1,0,0,2}
Knapsack1[n,weights,values,T]
Selected objects: {3,1}
Optimal value: 46
KnapsackSolve[{{30,6,1},{14,3,1},{16,4,1},{9,2,1}},10]
{1,0,1,0}
Example 3
Example 3
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Knapsack problem in package Wolfram Mathematica
by Predrag S. Stanimirović & Artem Stupin
Wolfram Community, STAFF PICKS, August 8, 2025
https://community.wolfram.com/groups/-/m/t/3527396
by Predrag S. Stanimirović & Artem Stupin
Wolfram Community, STAFF PICKS, August 8, 2025
https://community.wolfram.com/groups/-/m/t/3527396