0/1 Knapsack

A museum curator needs to select artifacts to display, maximizing their cultural value while staying within the exhibit's weight limit. This is a variation of the classic knapsack problem.

dynamic programmingknapsack problemoptimizationrecursionmemoization

Problem Statement

You are a museum curator preparing a new exhibit. You have a collection of artifacts, each with a cultural value and a weight. The exhibit space can only support a certain maximum weight. Given the maximum weight capacity of the exhibit and a list of artifacts with their corresponding cultural values and weights, determine the maximum total cultural value of the artifacts you can include in the exhibit without exceeding the weight limit.

Example 1

Input: capacity = 10, weights = [6, 3, 4, 2], values = [30, 14, 16, 9]

Output: 46

The optimal selection is artifacts with values 30, 14, and 2, totaling 46, and weights 6, 3, and 1, totaling 9, which is within the capacity of 10.

Example 2

Input: capacity = 5, weights = [1, 2, 3, 2, 2], values = [8, 4, 0, 5, 3]

Output: 13

The optimal selection is artifacts with values 8 and 5, totaling 13, and weights 1 and 2, totaling 3, which is within the capacity of 5.

Constraints

-1 <= capacity <= 1000
-1 <= number of artifacts <= 100
-1 <= weight of each artifact <= 1000
-1 <= cultural value of each artifact <= 1000

Brute Force Approach

The brute force approach would involve checking every possible combination of artifacts to see which combination yields the highest total cultural value without exceeding the weight capacity. It's like trying every possible subset of artifacts and calculating the total value and weight for each, then picking the best one. This quickly becomes inefficient as the number of artifacts increases.

TimeO(2^n)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem