Knapsack solves knapsack problem return maxProfit
(maxWeight int, weights, values []int)
| 18 | // Knapsack solves knapsack problem |
| 19 | // return maxProfit |
| 20 | func Knapsack(maxWeight int, weights, values []int) int { |
| 21 | n := len(weights) |
| 22 | m := maxWeight |
| 23 | // create dp data structure |
| 24 | dp := make([][]int, n+1) |
| 25 | for i := range dp { |
| 26 | dp[i] = make([]int, m+1) |
| 27 | } |
| 28 | for i := 0; i < len(weights); i++ { |
| 29 | for j := 0; j <= maxWeight; j++ { |
| 30 | if weights[i] > j { |
| 31 | dp[i+1][j] = dp[i][j] |
| 32 | } else { |
| 33 | dp[i+1][j] = Max(dp[i][j-weights[i]]+values[i], dp[i][j]) |
| 34 | } |
| 35 | } |
| 36 | } |
| 37 | return dp[n][m] |
| 38 | } |
| 39 | |
| 40 | /* |
| 41 | func main() { |