Value of optimal combination of objects

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Combination Value
Click For Summary

Discussion Overview

The discussion revolves around the Knapsack problem, specifically focusing on finding the optimal combination of objects that can fit into a knapsack of a given weight capacity, $W$. Participants explore the formulation of the problem, the recursive relationship for determining the maximum value, and the implications of having an infinite number of each object versus a limited supply.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • Some participants propose the recursive formula $$K(w)=\max_{w_i \leq w} \{ K(w-w_i)+v_i\}$$ as a means to express the value of the optimal combination of objects with total weight $w$.
  • One participant suggests that if object $i$ is the last added to the optimal combination, then the remaining weight $w-w_i$ must also represent an optimal combination.
  • There is a discussion about calculating specific values, such as $K(1)$ and $K(2)$, with participants attempting to derive these values based on the weights and values of the objects.
  • Participants express interest in creating a table to visualize the values of $K(w)$ for different weights and to track the optimal combinations.
  • One participant raises a question about how the approach changes if there is only one of each object available, leading to the introduction of a new recursive formula for that scenario.
  • There is a suggestion that the table created can be used not only to find the maximum value but also to determine which specific objects contribute to that value.

Areas of Agreement / Disagreement

Participants generally agree on the formulation of the problem and the recursive approach, but there are multiple views on how to handle the case of limited objects. The discussion remains unresolved regarding the implications of having a finite versus infinite supply of objects.

Contextual Notes

Participants have not fully resolved the mathematical steps involved in transitioning from the infinite case to the finite case, and there are assumptions about the weights and values of the objects that are not explicitly defined.

  • #31
I like Serena said:
Suppose we had 2 identical objects with place for only 1 of them.
Then we would have 2 solutions.

Of suppose we had objects with weights 1 and 4, and also objects with weights 2 and 3, both adding up to the same value.
Then, if we only had a weight allowance of 5, we would still have 2 solutions. (Nerd)

I understand! Thank you very much! (Clapping)(Smirk)
 

Similar threads

Graduate How to combine correlated vector-valued estimates
  • · Replies 11 ·
Replies
11
Views
3K
MHB Versions of the Knapsack problem
  • · Replies 1 ·
Replies
1
Views
1K
MHB Solving Knapsack Problem: 1st & 2nd Algorithm
  • · Replies 1 ·
Replies
1
Views
2K
MHB Vector Space - Proving Associativity
  • · Replies 4 ·
Replies
4
Views
2K
MHB Understanding Gauss Quadrature for Approximating Integrals
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Inner and Outer Product of the Wavefunctions
  • · Replies 8 ·
Replies
8
Views
4K
MHB Understanding the Theorem for Feasible Solutions of Difference Constraints
  • · Replies 15 ·
Replies
15
Views
3K
Graduate Large weighted least squares system
  • · Replies 4 ·
Replies
4
Views
1K
How Does the Direct Sum Relate to Unique Decomposition in Vector Spaces?
  • · Replies 1 ·
Replies
1
Views
2K
MHB What is the intersection of two spans?
  • · Replies 8 ·
Replies
8
Views
3K