For the concurrent programming paradigm, implement the brute force solution of the knapsack problem in GoLang. Below is a regular recursive solution (with a single thread) in Go. Use concurrency in order to accelerate the resolution of this problem. Since the brute force approach consists in exploring the binary solution tree, a first approach would be to subdivide the problem into two parts, the left sub-tree and the right sub-tree, and to create two threads in order to concurrently solve these subproblems. Once these two threads completed, only the best solution is kept.

package main

import "fmt" import "time" import "runtime"

func Max(x, y int) int { if x < y { return y } return x }

/***

last := len(weights)-1 // best solution with the last item go KnapSack(W - weights [last], weights [:last], values [:last]) // best solution without the last item go KnapSack(W, weights [:last], values [:last]) // code here to synchronize and then determine which one is the best solution

***/ // Returns the maximum value that // can be put in a knapsack of capacity W func KnapSack(W int, wt []int, val []int) int {

// Base Case if (len(wt) == 0 || W == 0) { return 0 } last := len(wt)-1

// If weight of the nth item is more // than Knapsack capacity W, then // this item cannot be included // in the optimal solution if wt[last] > W { return KnapSack(W, wt[:last], val[:last])

// Return the maximum of two cases: // (1) nth item included // (2) item not included } else { return Max(val[last] + KnapSack(W - wt[last], wt[:last], val[:last]), KnapSack(W, wt[:last], val[:last])) } }

// Driver code func main() {

fmt.Println("Number of cores: ",runtime.NumCPU()) // simple example W:= 7 weights := []int{1,2,3,5} values := []int{1,6,10,15} start := time.Now(); fmt.Println(KnapSack(W, weights , values)) end := time.Now(); fmt.Printf("Total runtime: %s ", end.Sub(start))

}