Victor Ferman
Soving knapsack problem
Revision 1:39e36a5c11e0, committed 2022-03-28
- Comitter:
- vferman
- Date:
- Mon Mar 28 20:21:44 2022 +0000
- Parent:
- 0:1ea8993f6b18
- Commit message:
- Push
Changed in this revision
| main.cpp | Show annotated file Show diff for this revision Revisions of this file |
--- a/main.cpp Tue Oct 20 03:54:08 2015 +0000
+++ b/main.cpp Mon Mar 28 20:21:44 2022 +0000
@@ -1,53 +1,117 @@
#include "mbed.h"
#include "rtos.h"
+#include <queue>
-DigitalOut led1(LED1);
-DigitalOut led2(LED2);
-DigitalOut led3(LED3);
-uint32_t button_pressed;
-Thread *thread2;
-Thread *thread3;
-Thread *thread4;
-Thread *thread5;
-Thread *thread6;
+
+//#define DELAY_INSIDE
+//#define DELAY_BTWN
+#define DELAY_DISPLAY
+
+#define DELAY_INSIDE_TIME 1000
+#define DELAY_BTWN_TIME 311
+#define DELAY_DISPLAY_TIME 100
+
-osMutexDef (mutex_1); // Declare mutex
-osMutexId (mutex_1_id); // Mutex ID
-
-osMutexDef (mutex_2); // Declare mutex
-osMutexId (mutex_2_id); // Mutex ID
+#define ARRAY_SIZE 16
+#define THREAD_ARRAY_SIZE 10
+
+typedef struct{
+ int tid;
+ int pid;
+ int cap;
+ int weights[ARRAY_SIZE];
+ int values[ARRAY_SIZE];
+ int ts_begin;
+ int ts_end;
+ int proc_time;
+ int n;
+}problema;
-osMessageQDef(message_q, 10, uint32_t); // Declare a message queue
-osMessageQId (message_q_id); // Declare an ID for the message queue
-Serial pc(USBTX, USBRX);
-
-struct Problema
-{
+typedef struct{
int tid;
int pid;
int cap;
- int weights[30];
- int values[30];
+ int weights[ARRAY_SIZE];
+ int values[ARRAY_SIZE];
int ts_begin;
int ts_end;
int proc_time;
-};
+ int opt;
+}solucion;
+
+
+Timer t;
+DigitalOut led1(LED1); // Red
+DigitalOut led2(LED2); // Green
+DigitalOut led3(LED3); // Blue
+
+osMutexDef (mutex_leds);//mutex for LEDs
+osMutexDef (mutex_p); //problem queue mutex
+osMutexDef (mutex_s); //solution queue mutex
-int printP(struct Problema p){
+
+osMutexId (mutex_leds_id); // LED mutex ID
+osMutexId (mutex_p_id); // problem queue mutex ID
+osMutexId (mutex_s_id); // solution queue mutex ID
+
+
+queue <problema> problem_q;
+queue <solucion> solution_q;
+
+Serial pc(USBTX, USBRX);
+
+#ifdef DEBUG
+int printP(problema p){
int i;
- printf("\n--------------------\n");
- printf("pid: %i\n", p.pid);
- printf("tid: %i\n", 0);
- printf("cap: %i\n", p.cap);
- printf("W \t V\n");
+ printf("\n#P \t#T \tCap \t#items");
+ printf("\n%i \t%i \t%i \t%i\n",p.pid,p.tid,p.cap,p.n);
+ printf(" Weights \tValues\n");
+ printf(" ------- \t------\n");
i=0;
- while (p.weights[i]>=0 && p.values[i]>=0){
- printf("%i \t %i\n", p.weights[i],p.values[i]);
+ while (p.weights[i]>-5 && p.values[i]>-5 && i<30){
+ printf("%i. %i \t%i\n", i+1, p.weights[i],p.values[i]);
i++;
}
-
+ printf("\n");
+ return 1;
+}
+
+int printS(solucion s){
+ int i;
+ printf("\n#S \t#T \tCap \tOpt Val \tBegin \t\tEnd \t\tProc");
+ printf("\n%i \t%i \t%i \t%i \t\t%ius \t%ius \t%ius\n", s.pid, s.tid, s.cap, s.opt, s.ts_begin, s.ts_end, s.proc_time);
+ printf(" Weights \tValues \t(included items)\n");
+ printf(" ------- \t------\n");
+ i=0;
+ while (s.weights[i]>-5 && s.values[i]>-5 && i<30){
+ printf("%i. %i \t%i\n", i+1, s.weights[i],s.values[i]);
+ i++;
+ }
+ printf("\n");
return 1;
}
+
+#else
+#endif
+
+int printF(solucion s){
+ int i;
+ printf("\n#");
+ printf("%i,", s.tid);
+ printf("%i,", s.pid);
+ printf("%i", s.cap);
+ i=0;
+ while (s.weights[i]>=0 && s.values[i]>=0 && i<30){
+ printf(",%i,%i", s.weights[i],s.values[i]);
+ i++;
+ }
+ printf(",%i", s.ts_begin);
+ printf(",%i", s.ts_end);
+ printf(",%i", s.proc_time);
+ printf("*");
+ return 1;
+}
+
int my_atoi(char *str) {
int res = 0; // Initialize result
// Iterate through all characters of input string and update result
@@ -56,8 +120,45 @@
return res;
}
+// A utility function that returns maximum of two integers
+int max(int a, int b) { return (a > b)? a : b; }
+
+// Returns the maximum value that can be put in a knapsack of capacity W
+solucion knapSackP(problema p, int t){
+ solucion s;
+ s.ts_begin=t;//t.read_us();
+ int i, w,index=0;
+ int K[p.n+1][p.cap+1];
+ // Build table K[][] in bottom up manner
+ for (i = 0; i <= p.n; i++){
+ for (w = 0; w <= p.cap; w++){
+ if (i==0 || w==0)
+ K[i][w] = 0;
+ else if (p.weights[i-1] <= w)
+ K[i][w] = max(p.values[i-1] + K[i-1][w-p.weights[i-1]], K[i-1][w]);
+ else
+ K[i][w] = K[i-1][w];
+ }
+ }
+ s.opt = K[p.n][p.cap];
+
+ w = p.cap;
+ for (i=p.n; i>0; i--){
+ if(K[i][w] != K[i-1][w]){
+ //printf("(p.weights=%i,val=%i)-> ",p.weights[i-1],val[i-1]);
+ s.weights[index]=p.weights[i-1];
+ s.values[index++]=p.values[i-1];
+ w=w-p.weights[i-1];
+ }
+ }
+ s.weights[index]=-5;
+ s.values[index]=-5;
+
+
+ return s;
+}
+
void led_func(uint32_t n){
- //mutex
uint32_t temp = ~((n%7)+1);
led3 = temp&(uint32_t)1;
led2 = (temp&(uint32_t)2)>>1;
@@ -68,160 +169,220 @@
{
uint32_t cont =0;
while (true) {
+ osMutexWait(mutex_leds_id, osWaitForever); //request lock
led_func(cont);
+ osMutexRelease(mutex_leds_id); //unlock
Thread::wait((uint32_t)argument );
cont++;
}
}
-void count_thread(void const *argument)
-{
+void worker_thread(void const *argument){
+ problema p;
+ solucion s;
+
while (true) {
- osMutexWait(mutex_2_id, osWaitForever);
- button_pressed++;
- osMutexRelease(mutex_2_id);
+ osMutexWait(mutex_p_id, 1000);
+ if (!problem_q.empty()){
+ p = problem_q.front();
+ problem_q.pop();
+ osMutexRelease(mutex_p_id);
+
+ #ifdef DEBUG
+ p.tid = (uint32_t)argument;
+ printf("-------------------------------------------------------");
+ printP(p);
+ #endif
+
+ //printf("\nT1:%i\n",t.read_us());
+ s = knapSackP(p,t.read_us());
+ s.ts_end=t.read_us();
+ //printf("\nT2:%i\n",t.read_us());
+ s.proc_time=s.ts_end-s.ts_begin;
+ s.tid = (uint32_t)argument;
+ s.pid = p.pid;
+ s.cap = p.cap;
+
+ #ifdef DEBUG
+ printS(s);
+ #endif
+
+ osMutexWait(mutex_s_id, 1000);
+ solution_q.push(s);
+ osMutexRelease(mutex_s_id);
+
+ osMutexWait(mutex_leds_id, 1000); //request lock
+ led_func((uint32_t)argument);
+ osMutexRelease(mutex_leds_id); //unlock
+
+ }else{
+ osMutexRelease(mutex_p_id);
+ }
- osMutexWait(mutex_1_id, osWaitForever);
- osMessagePut(message_q_id, button_pressed, osWaitForever);
- osMutexRelease(mutex_1_id);
- Thread::wait(2000);
+ osThreadYield();
+ #ifdef DELAY_INSIDE
+ Thread::wait(DELAY_INSIDE_TIME);
+ #endif
}
}
int main(){
-
- char buffer_counter=0;
- char buffer[4];
- char input_char;
- buffer[0]='\0';
- buffer[3]='\0';
- char stage = 0;
- int number_threads=0;
- int i;
- pc.baud (115200);
- char parseFlag =1;
-
- struct Problema problemas[10];
- char problema_counter=0;
- char item_counter=0;
+ t.start();
+ problema *problemas_array; //array to store the parsed problems
+ Thread *threads_array[THREAD_ARRAY_SIZE]; //array to instance the threads
+ char buffer[4]; //buffer to atoi convertion
+ solucion s; // var to pop the solutions from solution queue
+ char input_char; //received char form serial input
+ char stage = 0; //State of the parsing loop
+ char parseFlag =1; //flag to exit the input loop
+ char displayFlag =1; //flag to exit the display solution loop
+ int i; //used to indexing alog the differents arrays
+ int number_threads; //number of threads recived
+ int number_threads_temp; //used to verify if we have recived the number of threads
+ char problema_counter; //problem counter
+ char item_counter; //
+ char buffer_counter; //used to indexing the buffer used to atoi convertion
+ pc.baud (115200); //Baudrate
- /*thread2 = new Thread(count_thread);
- thread3 = new Thread(count_thread);
- thread4 = new Thread(count_thread);
- thread5 = new Thread(count_thread);
- thread6 = new Thread(count_thread);
- osEvent event;*/
-
- /*message_q_id = osMessageCreate(osMessageQ(message_q), NULL);
- osEvent event = osMessageGet(message_q_id, osWaitForever);
-
- if (0== osMutexWait(mutex_1_id, 0)) {
- printf(" %d \n\r", event.value.p);
- }else{
- printf("Else \n\r");
- }
- osMutexRelease(mutex_1_id);
- */
while (true) {
+ problemas_array =(problema *) malloc(10*sizeof(problema)) ;
+ problema_counter=0;
+ number_threads=0;
+ item_counter=0;
+ buffer_counter=0;
+ buffer[0]='\0';
+ buffer[3]='\0';
+ i=0;
parseFlag=1;
- while(parseFlag){
- input_char = getchar();
- if (input_char=='&'){
+ displayFlag =1;
+ stage = 0;
+
+ while(parseFlag){ //input loop
+ input_char = getchar(); //receive char from Serial
+ //Parsing the message
+ if (input_char=='&'){ //start of message
buffer[0]='\0';
buffer_counter=0;
problema_counter=0;
item_counter=0;
number_threads=0;
stage = 1;
- printf("Stage %i\n", stage);
- }else if (input_char=='#'){
+ //printf("Stage %i\n", stage);
+ }else if (input_char=='#'){ //end of threads number
buffer[0]='\0';
buffer_counter=0;
stage = 2;
- printf("Stage %i\n", stage);
- }else if (input_char >= '0' && input_char <= '9'){
+ //printf("Stage %i\n", stage);
+ }else if (input_char >= '0' && input_char <= '9'){ //number received
buffer[buffer_counter++]=input_char;
buffer[buffer_counter]='\0';
- }else if (input_char=='*'){
+ }else if (input_char=='*'){ //end of line
if (stage==1){
- number_threads = my_atoi(&buffer[0]);
- printf("Number of threads = %i\n", number_threads);
- printf("Problema = %i\n", problema_counter);
+ number_threads_temp = my_atoi(&buffer[0]);
+ number_threads = (number_threads_temp>0 && number_threads_temp<=10)? number_threads_temp: 5;
+ //printf("Number of threads = %i\n", number_threads);
+ //printf("Problema = %i\n", problema_counter);
buffer[0]='\0';
buffer_counter=0;
}else if (stage==4){
- problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
+ problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
problema_counter++;
item_counter=0;
- printf("4Problema = %i\n", problema_counter);
+ //printf("4Problema = %i\n", problema_counter);
}else if (stage==5){
- problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
- problemas[problema_counter].values[item_counter]=-5;
- problemas[problema_counter].weights[item_counter]=-5;
+ problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
+ problemas_array[problema_counter].values[item_counter]=-5;
+ problemas_array[problema_counter].weights[item_counter]=-5;
+ problemas_array[problema_counter].n=item_counter;
problema_counter++;
item_counter=0;
- printf("Problema = %i\n", problema_counter);
+ //printf("Problema = %i\n", problema_counter);
}
- }else if (input_char==','){
+ }else if (input_char==','){ //delimiter do the message
if (stage==2){
- problemas[problema_counter].pid = my_atoi(&buffer[0]);
+ problemas_array[problema_counter].pid = my_atoi(&buffer[0]);
stage=3;
- printf("Stage %i\n", stage);
+ //printf("Stage %i\n", stage);
}else if (stage==3){
- problemas[problema_counter].cap = my_atoi(&buffer[0]);
+ problemas_array[problema_counter].cap = my_atoi(&buffer[0]);
stage=4;
- printf("Stage %i\n", stage);
+ //printf("Stage %i\n", stage);
} else if (stage==4){
- problemas[problema_counter].weights[item_counter]=my_atoi(&buffer[0]);
+ problemas_array[problema_counter].weights[item_counter]=my_atoi(&buffer[0]);
stage=5;
- printf("Stage %i\n", stage);
+ //printf("Stage %i\n", stage);
}else if (stage==5){
- problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
+ problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
stage=4;
- printf("Stage %i\n", stage);
+ //printf("Stage %i\n", stage);
}
buffer[0]='\0';
buffer_counter=0;
-
- }else if (input_char=='\n'){
+ }else if (input_char=='\n'){ //newline received
buffer[0]='\0';
buffer_counter=0;
- }else if (input_char=='X'){
+ }else if (input_char=='X'){ //end of message
buffer[0]='\0';
buffer_counter=0;
stage=0;
- printf("\nNumber of threads = %i\n", number_threads);
- for (i=0; i<problema_counter; i++) printP(problemas[i]);
- parseFlag =0;
+ //printf("\nNumber of threads = %i\n", number_threads);
+ fflush(stdout);
+ fflush(stdin);
+ parseFlag =0; //exit form input loop
}
}
- printf("\nNumber of threads = %i\n", number_threads);
- printf("\nNumber of problems = %i\n", problema_counter);
- printf("\n Finished \n");
- Thread thread(led_thread, (void *)1000);
- osDelay(6000);
- thread.terminate();
+ //printf("\nNumber of threads = %i", number_threads);
+ //printf("\nNumber of problems = %i", problema_counter);
+ printf("\n Parse Finished \n");
+
+ osMutexWait(mutex_p_id, osWaitForever); //request lock
+ for (i=0; i<problema_counter; i++){
+ problem_q.push(problemas_array[i]);
+ }
+ osMutexRelease(mutex_p_id); //unlock
+
+ free(problemas_array);
+
+ i=0;
+ while (i<number_threads){
+ threads_array[i]= new Thread(worker_thread,(void *)(i));
+ #ifdef DELAY_BTWN
+ Thread::wait(DELAY_BTWN_TIME);
+ #endif
+ i++;
+ }
+
+ #ifdef DELAY_DISPLAY
+ Thread::wait(DELAY_DISPLAY_TIME);
+ #endif
+
+
+ while(displayFlag){
+ displayFlag=0;
+ printf("\n&%i*",number_threads);
+
+ while(!solution_q.empty()){
+ osMutexWait(mutex_s_id, osWaitForever);
+ if (!solution_q.empty()){
+ s = solution_q.front();
+ solution_q.pop();
+ printF(s);
+ }
+ osMutexRelease(mutex_s_id);
+ }
+
+
+ }
+
+
+ //i=0;
+ //while (i<number_threads) threads_array[i];
+ free(threads_array);
+
+ //osMutexWait(mutex_leds_id, osWaitForever); //request lock
+ // led_func(6);
+ //osMutexRelease(mutex_leds_id); //unlock
}
}
-
-//osStatus status;
-//mutex_1_id = osMutexCreate(osMutex(mutex_1));
-//osMutexWait(mutex_1_id, osWaitForever);
-//if (0== osMutexWait(mutex_1_id, 0)) {
-//}else{
-// printf("Else \n\r");
-//}
-//osMutexRelease(mutex_1_id);
-//message_q_id = osMessageCreate(osMessageQ(message_q), NULL);
-//(mutex_1_id, osWaitForever);
-//osEvent event = osMessageGet(message_q_id, osWaitForever);
-//printf(" %d \n\r", event.value.p);
-//fflush(stdout);
-//osMutexRelease(mutex_1_id);
-//Thread::wait(100);
-//osMutexWait(mutex_2_id, 1000);
-//osMutexRelease(mutex_2_id);
-//printf("\n(%c)\n", input_char);
-//fflush(stdout);