Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Knapsack Problem: Dynamic Programming

In course

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

This lecture covers the concept of dynamic programming applied to the Knapsack Problem, focusing on finding the optimal solution by considering the total weight accumulated by items. It explains the process of building a directed acyclic graph and determining the optimal solution through dynamic programming. The lecture also discusses the smallest weight subset with a specific profit and presents algorithms for solving the Knapsack Problem efficiently.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (23)

Directed acyclic graph

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Tree (graph theory)

In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A polytree (or directed tree or oriented tree or singly connected network) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree.

Cycle (graph theory)

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree. A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).

Knapsack problem

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Related lectures (31)

DFS Continuation: Topological Sort

Covers topics like DFS output, edge classification, acyclic graphs, correctness, time analysis, SCCs, and the Topological Sort algorithm.

Bayesian Networks: Factorization and Sampling

Explains Bayesian Networks factorization and sampling methods using DAGs and Variable Elimination.

Causal Inference & Directed Graphs

Explores causal inference, directed graphs, and fairness in algorithms, emphasizing conditional independence and the implications of DAGs.

Causal Inference: Learning Graph Structures

Explores causal inference through learning graph structures for causal reasoning from observational data.

What is a Formal Proof?