Value of optimal combination of objects

[evinda]

Hey! (Wave)I am looking at the Knapsack problem. (Nerd)

We have a sack,that has a capacity of objects with total cost $W$.
There are $n$ objects with weights $ w_1, w_2, \dots ,w_n$ and values $ v_1, v_2, \dots , v_n$.

Which is the most valuable combination of elements,that fit in the sack,given that there is an infinite number of each object?

Let $K(w)$ the value of the optimal combination of objects with total weight $ w$.
We want to find $ K(W)$.We have to express it,with respect to the subproblems.

According to my notes,we use the following algorithm:

K(0)=0
for w=1 to W
    K(w)=max_{wi <= w} {K(w-wi)+vi}

Could you explain me why we use the formula:$$K(w)=\max_{w_i \leq w} \{ K(w-w_i)+v_i\}$$ to find the value of the optimal combination of objects with total weight $w$ ? (Thinking)

 

[I like Serena]

Hey! (Wave)I am looking at the Knapsack problem. (Nerd)

We have a sack,that has a capacity of objects with total cost $W$.
There are $n$ objects with weights $ w_1, w_2, \dots ,w_n$ and values $ v_1, v_2, \dots , v_n$.

Which is the most valuable combination of elements,that fit in the sack,given that there is an infinite number of each object?

Let $K(w)$ the value of the optimal combination of objects with total weight $ w$.
We want to find $ K(W)$.We have to express it,with respect to the subproblems.

According to my notes,we use the following algorithm:

K(0)=0
for w=1 to W
    K(w)=max_{wi <= w} {K(w-wi)+vi}

Could you explain me why we use the formula:$$K(w)=\max_{w_i \leq w} \{ K(w-w_i)+v_i\}$$ to find the value of the optimal combination of objects with total weight $w$ ? (Thinking)

Hi! (Blush)

Let's see what it says...

Suppose $K(w)$ is the optimal combination with weight $w$.
And suppose $i$ was the last object to go in.
Then before object $i$ went in, we must also have had an optimal combination.
In other words, $K(w-w_i)$ was an optimal combination with a value of $K(w) - v_i$.

How does that sound? (Thinking)

 

[evinda]

Hi! (Blush)

Let's see what it says...

Suppose $K(w)$ is the optimal combination with weight $w$.
And suppose $i$ was the last object to go in.
Then before object $i$ went in, we must also have had an optimal combination.
In other words, $K(w-w_i)$ was an optimal combination with a value of $K(w) - v_i$.

How does that sound? (Thinking)

I understand! (Smirk) Could you also give me an example,to show me how we can apply the formula? (Blush) (Thinking)

 

[I like Serena]

I understand! (Smirk) Could you also give me an example,to show me how we can apply the formula? (Blush) (Thinking)

Sure! (Wasntme)

What is the most value you can bring along with your knapsack? (Sweating)

Perhaps we should start with: what is $K(1)$? (Wondering)

 

[evinda]

Sure! (Wasntme)
What is the most value you can bring along with your knapsack? (Sweating)

Perhaps we should start with: what is $K(1)$? (Wondering)

Nice! (Cool)

Is it $K(1)=K(0)+v_1$ ? (Thinking)
$K(0)=0$,right?
And..do we choose the grey box,because of the fact that its value is greater that this of the orange box?
So,is it $v_1=2$ and $K(1)=2$ ? (Thinking)

 

[I like Serena]

Nice! (Cool)

Thank you! (Blush)

Is it $K(1)=K(0)+v_1$ ? (Thinking)
$K(0)=0$,right?
And..do we choose the grey box,because of the fact that its value is greater that this of the orange box?
So,is it $v_1=2$ and $K(1)=2$ ? (Thinking)

Yes, yes, yes, yes, and yes. ;)

To use your formula:
$$\begin{aligned}{\color{brown}K}(1)
&=\max({\color{brown}K}(1 - {\color{gray}w_{gray}}) + {\color{gray}v_{gray}},\
{\color{brown}K}(1 - {\color{orange}w_{orange}}) + {\color{orange}v_{orange}}) \\
&=\max({\color{brown}K}(1-1)+2, \ {\color{brown}K}(1-1)+1) \\
&= \max(0+2,\ 0+1) = 2
\end{aligned}$$Now... what about $K(2)$?
Wait! Maybe we could create a table? (Wondering)

 

[evinda]

Now... what about $K(2)$?

$$K(2)=\max \left\{\begin{matrix}
K(2-w_{\text{gray}})+v_{\text{gray}}=4\\
K(2-w_{\text{orange}})+v_{\text{orange}}=3\\
K(2-w_{\text{blue}})+v_{\text{blue}}=2
\end{matrix}\right. \left.\begin{matrix}
\\
\\

\end{matrix}\right\}=4$$

Wait! Maybe we could create a table? (Wondering)

That's what I have tried (Blush)

View attachment 3019

Is it right or have I done something wrong?(Thinking)

 

[I like Serena]

$$K(2)=\max \left\{\begin{matrix}
K(2-w_{\text{gray}})+v_{\text{gray}}=4\\
K(2-w_{\text{orange}})+v_{\text{orange}}=3\\
K(2-w_{\text{blue}})+v_{\text{blue}}=2
\end{matrix}\right. \left.\begin{matrix}
\\
\\

\end{matrix}\right\}=4$$

Good! (Happy)

That's what I have tried (Blush)
View attachment 3019
Is it right or have I done something wrong?(Thinking)

It looks good to me!

Here is my attempt. (Blush)
\(
\def\block#1#2#3#4{\color#1\colorbox{#2}{$\kern#3pt #4 \kern#3pt$}}
\def\one {\block{{RedOrange}}{Apricot}{0}{1}}
\def\two {\block{[gray]{0.3}}{LightGray}{0}{2}}
\def\three {\block{{blue}}{cyan}{6}{2}}
\def\four {\block{[rgb]{0.8,0.5,0.2}}{yellow}{12}{10}}
\def\five {\block{{DarkGreen}}{LightGreen}{36}{4}}
\)

\begin{array}{|c|c|c|}
\hline
w& 1 - 1 - 2 - 4 - 12\\
v& \one \two \three \four \five\\
\hline
w&&K \\
\hline
0 & & 0 \\
1 & \two& 2\\
2 &\two\two& 4\\
3 &\two\two\two & 6\\
4 & \four & 10 \\
5 & \four\two & 12 \\
6 & \four\two\two & 14 \\
7 & \four\two\two\two & 16 \\
8 & \four\four & 20 \\
\vdots & & \vdots \\
\hline
\end{array}

But I wasn't done yet! (Doh)

Btw, what if you do not have an infinite number of each object, but only one of each? (Wondering)

 

[evinda]

View attachment 3022It looks good to me!

(Happy) From this table,can we just find the value of the optimal combination of objects with total weight $W$,or can we also find which objects we have to take to get the optimal combination? (Thinking)

Here is my attempt. (Blush)
\(
\def\block#1#2#3#4{\color#1\colorbox{#2}{$\kern#3pt #4 \kern#3pt$}}
\def\one {\block{{RedOrange}}{Apricot}{0}{1}}
\def\two {\block{[gray]{0.3}}{LightGray}{0}{2}}
\def\three {\block{{blue}}{cyan}{6}{2}}
\def\four {\block{[rgb]{0.8,0.5,0.2}}{yellow}{12}{10}}
\def\five {\block{{DarkGreen}}{LightGreen}{36}{4}}
\)

\begin{array}{|c|c|c|}
\hline
w& 1 - 1 - 2 - 4 - 12\\
v& \one \two \three \four \five\\
\hline
w&&K \\
\hline
0 & & 0 \\
1 & \two& 2\\
2 &\two\two& 4\\
3 &\two\two\two & 6\\
4 & \four & 10 \\
5 & \four\two & 12 \\
6 & \four\two\two & 14 \\
7 & \four\two\two\two & 16 \\
8 & \four\four & 20 \\
\vdots & & \vdots \\
\hline
\end{array}

Could you explain me what you did at your table? (Blush) (Thinking)

Btw, what if you do not have an infinite number of each object, but only one of each? (Wondering)

According to my notes,we define $K(w,j)=\text{sack of weight } \leq w \text{ with the greatest value from the objects } 1,2 \dots j$

$$K(w,j)=\max \{ K(w-w_j,j-1)+v_j,K(w,j-1)\}$$

Could you explain me the above formula?(Blush)

 

[I like Serena]

(Happy) From this table,can we just find the value of the optimal combination of objects with total weight $W$,or can we also find which objects we have to take to get the optimal combination? (Thinking)

Yes... yes we can. (Poolparty)

We can do so by working backwards recursively.
The total value at $w=15$ is $K(15)=36$.
Since this is in the yellow column, the yellow object was added last.
So for starters, we have a yellow object.

The yellow object has weight $4$, so we go back to the optimal combination at $w=11$. We can choose either the gray column or the yellow column, since both contain the number $26$.
If we pick the yellow column, we extract again a yellow object with weight $4$.

And so on... (Nerd)

Could you explain me what you did at your table? (Blush) (Thinking)

I started at $w=1$ and figured out what the best object was to add, which was the gray one.
That gave me $K(1)=2$.
Then, for $K(2)$, I checked all objects of weight 1 and checked what K(1) plus their values was.
And I also checked all objects of weight 2 that might be added to K(0).
Turns out it was best to add another gray object for $K(2)=4$.
And so on... (Blush)

According to my notes,we define $K(w,j)=\text{sack of weight } \leq w \text{ with the greatest value from the objects } 1,2 \dots j$

$$K(w,j)=\max \{ K(w-w_j,j-1)+v_j,K(w,j-1)\}$$

Could you explain me the above formula?(Blush)

I'll give it a try... (Wasntme)

Object $j$ is either included in $K(w,j)$ or it is not.
If it is included, $K(w-w_j,j-1)$ must have been an optimal combination before we added object $j$.
If it is not included, the optimal combination won't change if we don't consider object $j$.

How does that sound? (Wondering)

 

[evinda]

Yes... yes we can. (Poolparty)

We can do so by working backwards recursively.
The total value at $w=15$ is $K(15)=36$.
Since this is in the yellow column, the yellow object was added last.
So for starters, we have a yellow object.

The yellow object has weight $4$, so we go back to the optimal combination at $w=11$. We can choose either the gray column or the yellow column, since both contain the number $26$.
If we pick the yellow column, we extract again a yellow object with weight $4$.

And so on... (Nerd)

I understand.. So,one possible combination is this one,right? (Malthe)

View attachment 3023

I started at $w=1$ and figured out what the best object was to add, which was the gray one.
That gave me $K(1)=2$.
Then, for $K(2)$, I checked all objects of weight 1 and checked what K(1) plus their values was.
And I also checked all objects of weight 2 that might be added to K(0).
Turns out it was best to add another gray object for $K(2)=4$.
And so on... (Blush)

Aha! (Nerd) I understand! (Yes)

I'll give it a try... (Wasntme)

Object $j$ is either included in $K(w,j)$ or it is not.
If it is included, $K(w-w_j,j-1)$ must have been an optimal combination before we added object $j$.
If it is not included, the optimal combination won't change if we don't consider object $j$.

How does that sound? (Wondering)

(Thinking) Could you also give me an example,so that I can see if I have understood it? (Blush)

 

[I like Serena]

I understand.. So,one possible combination is this one,right? (Malthe)

Yes.
It shows how you want as many yellow objects as possible, since it has the highest specific value of 2.5 \$/kg.
And continue with the next best specific value of 2.0 \$/kg, the gray objects, which uses up all available space. (Nerd)

(Thinking) Could you also give me an example,so that I can see if I have understood it? (Blush)

Perhaps you can explain what you have understood? (Wondering)

 

[evinda]

Yes.
It shows how you want as many yellow objects as possible, since it has the highest specific value of 2.5 \$/kg.
And continue with the next best specific value of 2.0 \$/kg, the gray objects, which uses up all available space. (Nerd)

So,since we want as many yellow objects as possible,is this the best combination? (Thinking)

View attachment 3024

Perhaps you can explain what you have understood? (Wondering)

We want to determine if we have to pick the $j^{th}$ object,or not..If it is valuabe and we decide to take it,then we add at the value of the optimal combination of the first $j-1$ objects, the value of the $j^{th}$ object,if we don't take it,we have by now the value of the optimal combination of the first $j-1$ objects. (Thinking) (Blush)

 

[I like Serena]

So,since we want as many yellow objects as possible,is this the best combination? (Thinking)

Yes it is.

Your previous combination was also a best combination.
It had exactly the same number of yellow and gray objects, just in a different order. (Happy)

We want to determine if we have to pick the $j^{th}$ object,or not..If it is valuabe and we decide to take it,then we add at the value of the optimal combination of the first $j-1$ objects, the value of the $j^{th}$ object,if we don't take it,we have by now the value of the optimal combination of the first $j-1$ objects. (Thinking) (Blush)

Sounds good!

How about applying it to the example?
What would for instance $K(1,1)$ to $K(1,5)$ be? (Wondering)

 

[evinda]

Yes it is.

Your previous combination was also a best combination.
It had exactly the same number of yellow and gray objects, just in a different order. (Happy)

Oh,yes!Nice! (Whew)

How about applying it to the example?
What would for instance $K(1,1)$ to $K(1,5)$ be? (Wondering)

Isn't it like that?

$$K(1,1)=\max \{ K(1-w_{\text{gray}},0)+v_{\text{gray}},K(1,0)\}=\max \{2,0 \}=2 \\ K(1,2)=\max \{ K(1-w_{\text{orange}},1)+v_{\text{orange}},K(1,1)\}=\max \{1,2 \}=2 \\ K(1,3)=K(1,2)=2 (\text{ since } K(1-w_{\text{blue}})\text{ is not well-defined)} \\ K(1,4)=K(1,3)=2 \\ K(1,5)=K(1,4)=2$$

(Thinking)

Do we conclude from the above that we choose firstly the gray box,and now the left boxes are the orange one,the blue one,the yellow one and the green one? Or am I wrong? (Thinking)

 

[I like Serena]

Isn't it like that?

$$K(1,1)=\max \{ K(1-w_{\text{gray}},0)+v_{\text{gray}},K(1,0)\}=\max \{2,0 \}=2 \\ K(1,2)=\max \{ K(1-w_{\text{orange}},1)+v_{\text{orange}},K(1,1)\}=\max \{1,2 \}=2 \\ K(1,3)=K(1,2)=2 (\text{ since } K(1-w_{\text{blue}})\text{ is not well-defined)} \\ K(1,4)=K(1,3)=2 \\ K(1,5)=K(1,4)=2$$

(Thinking)

Yep. It is. (Happy)

Do we conclude from the above that we choose firstly the gray box,and now the left boxes are the orange one,the blue one,the yellow one and the green one? Or am I wrong? (Thinking)

For $K(1,j)$ that is certainly the case... (Mmm)

How about $K(2,j)$, $K(3,j)$, and $K(4,j)$? (Sweating)

 

[evinda]

How about $K(2,j)$, $K(3,j)$, and $K(4,j)$? (Sweating)

I tried to create again a table:

View attachment 3034

Is it right? (Thinking)

Also,do I have to find $K(i,j), \forall i \in \{ 1, \dots, 15\}$ ? (Thinking) Because,I noticed that,after having found $15$,the results didn't change.. (Thinking) (Blush)

 

[I like Serena]

I tried to create again a table:

Is it right? (Thinking)

I only see a mistake in K(6,4) and K(6,5), which should both be 13.
Otherwise it looks good! (Smile)

Also,do I have to find $K(i,j), \forall i \in \{ 1, \dots, 15\}$ ? (Thinking) Because,I noticed that,after having found $15$,the results didn't change.. (Thinking) (Blush)

You still have to find them, since you ultimately want to know $K(15,5)$.
But yeah, effectively there's a lot of the knapsack's capacity we can't use. (Doh)

Here is my version. (Blush)
\(
\def\block#1#2#3#4{\color#1\colorbox{#2}{$\kern#3pt #4 \kern#3pt$}}
\def\one {\block{{RedOrange}}{Apricot}{0}{1}}
\def\two {\block{[gray]{0.3}}{LightGray}{0}{2}}
\def\three {\block{{blue}}{cyan}{6}{2}}
\def\four {\block{[rgb]{0.8,0.5,0.2}}{yellow}{16}{10}}
\def\five {\block{{DarkGreen}}{LightGreen}{68}{4}}
\)

\begin{array}{|c|c|c|}
\hline
w& 1 - 1 - 2 - 4 - 12\\
v& \one \two \three \four \\
&\five\\
\hline
w&&K \\
\hline
0 & & 0 \\
1 & \two& 2\\
2 &\two\one& 3\\
3 &\three\two & 4\\
4 & \four & 10 \\
5 & \four\two & 12 \\
6 & \four\two\one & 13 \\
7 & \four\three\two & 14 \\
8 & \four\three\two\one & 15 \\
\vdots &\cdots & \vdots \\
15 & \four\three\two\one & 15 \\
\hline
\end{array}

 

[evinda]

I only see a mistake in K(6,4) and K(6,5), which should both be 13.

Oh,yes! You are right! (Nod) It is:

$$K(6,4)=\max \{K(6-4,3)+10,K(6,3)\}=\max \{K(2,3)+10,K(6,3)\}=\max \{13,5\}=13$$

$$K(6,5)=K(6,4)=13$$

You still have to find them, since you ultimately want to know $K(15,5)$.

A ok...

But yeah, effectively there's a lot of the knapsack's capacity we can't use. (Doh)

How do we see that there's a lot of the knapsack's capacity we can't use? (Thinking)

Here is my version. (Blush)
\(
\def\block#1#2#3#4{\color#1\colorbox{#2}{$\kern#3pt #4 \kern#3pt$}}
\def\one {\block{{RedOrange}}{Apricot}{0}{1}}
\def\two {\block{[gray]{0.3}}{LightGray}{0}{2}}
\def\three {\block{{blue}}{cyan}{6}{2}}
\def\four {\block{[rgb]{0.8,0.5,0.2}}{yellow}{16}{10}}
\def\five {\block{{DarkGreen}}{LightGreen}{68}{4}}
\)

\begin{array}{|c|c|c|}
\hline
w& 1 - 1 - 2 - 4 - 12\\
v& \one \two \three \four \\
&\five\\
\hline
w&&K \\
\hline
0 & & 0 \\
1 & \two& 2\\
2 &\two\one& 3\\
3 &\three\two & 4\\
4 & \four & 10 \\
5 & \four\two & 12 \\
6 & \four\two\one & 13 \\
7 & \four\three\two & 14 \\
8 & \four\three\two\one & 15 \\
\vdots &\cdots & \vdots \\
15 & \four\three\two\one & 15 \\
\hline
\end{array}

Nice! (Yes)

How can we see from this table which is the best combination? (Thinking)

View attachment 3036

 

[I like Serena]

How do we see that there's a lot of the knapsack's capacity we can't use? (Thinking)

We can carry a total weight of 15 kg, but the optimum we found is only 8 kg.
Ah well, I guess we'll travel light then. (Mmm)

How can we see from this table which is the best combination? (Thinking)

Can you follow the trail backward from the end? (Wondering)

 

[evinda]

Ah well, I guess we'll travel light then. (Mmm)

(Bigsmile)

Can you follow the trail backward from the end? (Wondering)

So,is this one best combination?
View attachment 3037

And..this is an other one,right? (Thinking)

View attachment 3038

 

[I like Serena]

The optimal value is $K(15,5)=15$.
The first time we found this optimal value was at $K(8,4)=15$.
How did we find it?
Where were we coming from?
Which object was added? (Wondering)

 

[evinda]

The optimal value is $K(15,5)=15$.
The first time we found this optimal value was at $K(8,4)=15$.
How did we find it?
Where were we coming from?
Which object was added? (Wondering)

$$K(8,4)=\max \{ K(8-4,3)+10,K(8,3) \}=\max \{ K(4,3)+10,K(8,3)\}\\ =\max \{ 5+10,5 \}=\max \{ 15,5\}=15$$

So,we added the yellow box,in order to get $15$,right? (Smile)

 

[I like Serena]

$$K(8,4)=\max \{ K(8-4,3)+10,K(8,3) \}=\max \{ K(4,3)+10,K(8,3)\}\\ =\max \{ 5+10,5 \}=\max \{ 15,5\}=15$$

So,we added the yellow box,in order to get $15$,right? (Smile)

Yep. (Happy)
So we came from K(4,3) and added the yellow box.
And before that?

 

[evinda]

Yep. (Happy)
So we came from K(4,3) and added the yellow box.
And before that?

$$K(4,3)=\max \{ K(4-2,2)+2,K(4,2)\}=\max \{ K(2,2)+2,K(4,2) \}=\max \{5,3 \}=5$$

$$K(2,2)=\max \{ K(2-1,1)+1,K(2,1) \}=\max \{ K(1,1)+1,K(2,1) \}=\max \{ 3,2\}=3$$

$$K(1,1)=\max \{ K(0,0)+2,K(1,0)\}=\{ 2,0 \}=2$$

So,is this one best combination? (Thinking)

View attachment 3039

But..what if we start with the green box? (Thinking)

View attachment 3040

It is:
$$K(8,5)=\max \{ K(3,4)+4,K(8,4)\}=\max \{ 8,15\}=15$$

Does this mean,than we cannot take the green box,to have a best combination? (Thinking) Or am I wrong? (Thinking)

 

[I like Serena]

$$K(4,3)=\max \{ K(4-2,2)+2,K(4,2)\}=\max \{ K(2,2)+2,K(4,2) \}=\max \{5,3 \}=5$$

$$K(2,2)=\max \{ K(2-1,1)+1,K(2,1) \}=\max \{ K(1,1)+1,K(2,1) \}=\max \{ 3,2\}=3$$

$$K(1,1)=\max \{ K(0,0)+2,K(1,0)\}=\{ 2,0 \}=2$$

So,is this one best combination? (Thinking)

Yep!

But..what if we start with the green box? (Thinking)

It is:
$$K(8,5)=\max \{ K(3,4)+4,K(8,4)\}=\max \{ 8,15\}=15$$

Hold on. The green box weighs 12 kg. So you'd come from $K(-4,4)$ instead of $K(3,4)$. (Wasntme)

Does this mean,than we cannot take the green box,to have a best combination? (Thinking) Or am I wrong? (Thinking)

So no, we don't want the green box.
It's too heavy for too little value. (Speechless)

 

[evinda]

Hold on. The green box weighs 12 kg. So you'd come from $K(-4,4)$ instead of $K(3,4)$. (Wasntme)

Oh,yes! You are right! (Blush)

So no, we don't want the green box.
It's too heavy for too little value. (Speechless)

A ok! I tried to start with $T(9,4)$ and got the same combination. (Wait)

$$K(9,4)=\max \{ K(5,3)+10,K(9,3) \}=\max \{5+10,5\}=\max \{15,5 \}=15$$

$$K(5,3)=\max \{ K(3,2)+2,K(5,2)\}=\max \{ 5,3\}=5$$

$$K(3,2)=\max \{ K(2,1)+1,K(3,1)\}=\max \{ 3,2\}=3$$

$$K(2,1)=\max \{ K(1,0)+2,K(2,0)\}=\max \{ 2,0\}=2$$

View attachment 3041

So..this is the only best combination,right? (Thinking) Since,there is only one of each object,or not? (Blush)

 

[I like Serena]

I tried to start with $T(9,4)$ and got the same combination. (Wait)

$$K(9,4)=\max \{ K(5,3)+10,K(9,3) \}=\max \{5+10,5\}=\max \{15,5 \}=15$$

$$K(5,3)=\max \{ K(3,2)+2,K(5,2)\}=\max \{ 5,3\}=5$$

$$K(3,2)=\max \{ K(2,1)+1,K(3,1)\}=\max \{ 3,2\}=3$$

$$K(2,1)=\max \{ K(1,0)+2,K(2,0)\}=\max \{ 2,0\}=2$$

So..this is the only best combination,right? (Thinking) Since,there is only one of each object,or not? (Blush)

Yes. There is only one best combination.
And yes, you can deduce this from your table in more than 1 way. (Cash)

 

[evinda]

Yes. There is only one best combination.
And yes, you can deduce this from your table in more than 1 way. (Cash)

I understand! (Happy)

Has the fact that there is only one best combination to do with the specific example,or do we always have only one best combination,knowing that there is exactly one of each element? (Thinking)

 

[I like Serena]

I understand! (Happy)

Good! (Smile)

Has the fact that there is only one best combination to do with the specific example,or do we always have only one best combination,knowing that there is exactly one of each element? (Thinking)

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)

 

[evinda]

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)