<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April 24, 2025 08:39:56">April 24, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April 24, 2025 08:47:53">April 24, 2025</span>&emsp;

<td><ahref="/dynamic_programming/knapsack.md">0-1 Knapsack</a></td>

<td><ahref="https://cp-algorithms.com/dynamic_programming/knapsack.html">0-1 Knapsack</a></td>

<td>Given<spanclass="arithmatex">$W$</span>,<spanclass="arithmatex">$N$</span>, and<spanclass="arithmatex">$N$</span> items with weights<spanclass="arithmatex">$w_i$</span> and values<spanclass="arithmatex">$v_i$</span>, what is the maximum<spanclass="arithmatex">$\sum_{i=1}^{k} v_i$</span> for each subset of items of size<spanclass="arithmatex">$k$</span> (<spanclass="arithmatex">$1 \le k \le N$</span>) while ensuring<spanclass="arithmatex">$\sum_{i=1}^{k} w_i \le W$</span>?</td>

<td>Subset Sum</td>

<td>Given<spanclass="arithmatex">$N$</span> integers and<spanclass="arithmatex">$T$</span>, determine whether there exists a subset of the given set whose elements sum up to the<spanclass="arithmatex">$T$</span>.</td>

<td><ahref="/dynamic_programming/longest_increasing_subsequence.md">Longest Increasing Subsequence (LIS)</a></td>

<td><ahref="https://cp-algorithms.com/dynamic_programming/longest_increasing_subsequence.html">Longest Increasing Subsequence (LIS)</a></td>

<td>You are given an array containing<spanclass="arithmatex">$N$</span> integers. Your task is to determine the LIS in the array, i.e., a subsequence where every element is larger than the previous one.</td>

<h2id="related-topics">Related Topics<aclass="headerlink"href="#related-topics"title="Permanent link">&para;</a></h2>

<li><ahref="/dynamic_programming/profile-dynamics.md">Bitmask Dynamic Programming</a></li>

<li><ahref="https://cp-algorithms.com/dynamic_programming/profile-dynamics.html">Bitmask Dynamic Programming</a></li>

<li>Digit Dynamic Programming</li>

<li>Dynamic Programming on Trees</li>