$($Please use one of the emulators listed to send the FINAL CODE$)$This lab assignment is a variation on the $$Knapsack Problem$$lab exercise from a couple of weeks ago. The input is the same as in the lab exercise, but the processing and output are different.

Your program must start with the following heading:

; CS$130$Lab Assignment $5$Section xxxxx Last, First

; Emulator used: yyyyyy

You must replace xxxxx with your section number, Last and First with your name, and yyyyy with the emulator or other platform used $($VisUAL$,$ARMsim$,$ Mac, Raspberry Pi$,$et cetera$).$ You will have points taken off if the heading is not correct. Also, failure to list the emulator correctly will cause your lab to be graded last.

Your program must have two functions. One is named knapsack and operates similarly to the earlier lab exercise. The other is named sort and will be called from the knapsack function.

Input: The address of an array holding a set of triplets of values:

$$A weight

$$A value

$$A chosen indicator, $0$for not chosen, $1$for chosen

This address will be passed to your function in register $0$as a three$-$dimensional integer array containing the weight and value of each item you may wish to place in the knapsack. The function must be named knapsack.

Also, you will receive a parameter m in register $1,$which represents the maximum weight you can carry.

The end of the array will be marked with a special value of $-999.$

Typical input for an afternoon hike with supper:

Weight Value Chosen Possible Item

$520$Can of beans

$290$Can opener

$330$Silverware

$470$Can of beef stew

$850$Bottle of wine

$1100$Matches

$280$Can of Vienna sausage

$-999$ end of list

Maximum weight: $20$

Knapsack Output:

$$Updated entries in the $$Chosen$$column in the original array

$$The total value of your choices in register $0$

You do not have to perform any special linear programming as discussed in the earlier lab exercise. But your knapsack function must call a sort function, described below.

Sort Function:

This function receives the address of the array of triplets originally passed to the knapsack function. Its purpose is to sort the array into the desired sequence. You may sort the array entries by weight $($first column$)$or value $($second column$).$ You may sort the entries into ascending sequence or descending sequence.

Use your CS$116$C$++$language course textbook to determine how to sort an array if your introductory programming course did not cover that. Also, you may use Wikipedia, cplusplus.com, cppreference.com, or any other internet reference you desire to develop the sorting code. $($Most online examples are for sorting a single$-$column array, and you will almost certainly have to modify any example you find.$)$

Function Headings

Functions in any language should have a heading which gives some details of the function. The following is an example for VisUAL:

; knapsack function

; input: Table address in R$0$

; Maximum weight in R$1$

; Output: Actual total weight for selected items

; Purpose: Scans an array of integer values $($weight$,$value$,$

; selected$)$and chooses which items to include in the knapsack.

; Items are selected by ; putting a value of $1$in the

; $$selected$$column$.$

; Register usage:

; R$0,$R$1=$parameters as listed above

; $...$other registers as used

It is usually a good idea to list any special starting conditions, input limits$,$acceptable ranges of input values, or similar information as part of the heading. You will have points deducted if you do not include an appropriate heading similar to the above for both the knapsack and the sort functions.

Processing

Your knapsack function will be called by the sample test driver program shown later. It will call the sort function to sort the table $($called theArray in the test driver program$).$ You may sort by weight or by value.

When the sort function returns to the knapsack function, the knapsack function should move a $1$into the third variable $($Chosen$)$into the entries you want to select. Rather than doing any complex linear programming, you may sort the table by weight, then add in items until the weight limit is met, or sort the table by value, adding in the highest value items until the weight limit is met.

Sample Test Driver Program

; Knapsack lab exercise Sample main driver program

$$ ADR R$0,$theArray

$$ ADR R$12,$workArea

$$ LDR R$1,[$R$12,$#$4]$ ; maxWeight

$$ BL knapsack

$$ END

workArea DCD $0$

maxWeight DCD $25$

; Weight,Value,Chosen

theArray DCD $5,2,0$

a$2$ DCD $2,9,0$

a$3$ DCD $3,3,0$

a$4$ DCD $4,7,0$

a$5$ DCD $8,5,0$

a$6$ DCD $1,10,0$

a$7$ DCD $2,8,0$

last DCD $-999$

$$ ; YOUR CODE GOES HERE

knapsack

$$ MOV PC$,$LR ;return