Exercise: Knapsack Problems

labuladongOriginalAbout 5223 words

Prerequisite Knowledge

Before reading this article, you should first learn about:

Core Framework of Dynamic Programming
0-1 Knapsack Problem
Equal Subset Partition
Complete Knapsack Problem

The knapsack problem is a classic type of dynamic programming problem, focusing on selecting the optimal combination of elements within certain constraints.

Its main characteristic is the way the dp array is defined. The first dimension is defined as "using only the first i items," and subsequent dimensions are used to define the constraints.

For example, in the classic 0-1 Knapsack Problem, the dp array is defined as follows:

// Definition: dp[i][j] represents the maximum value achievable with the first i items and a knapsack capacity of j
int[][] dp = new int[N + 1][W + 1];

Below are some problems related to the knapsack problem to help deepen your understanding.

Exercise: Knapsack Problems

1049. 最后一块石头的重量 II https://leetcode.cn/problems/last-stone-weight-ii

1049. Last Stone Weight II https://leetcode.com/problems/last-stone-weight-ii

474. 一和零 https://leetcode.cn/problems/ones-and-zeroes

474. Ones and Zeroes https://leetcode.com/problems/ones-and-zeroes

3180. 执行操作可获得的最大总奖励 I https://leetcode.cn/problems/maximum-total-reward-using-operations-i

3180. Maximum Total Reward Using Operations I https://leetcode.com/problems/maximum-total-reward-using-operations-i