Develop a simple heuristic $($I recommend a construction or destruction heuristic$)$ in either R or Python to solve the following knapsack problem: $($Note$,$ this problem can be solved to optimality using integer programming; however, the focus of this question is on developing a heuristic and metaheuristic$).$ Then, develop a metaheuristic using your heuristic as a subroutine. You can iterate the heuristic n times and return the best solution, prevent previous solutions from being selected, etc. I am evaluating your ability to find a solution quickly with a heuristic and your approach to improve the heuristic with a metaheuristic.

Maximize $12$x$1+16$x$2+22$x$3+8$x$4$

S$.$T$.4$x$1+5$x$2+7$x$3+3$x$4<=140$

$0<=$ xi $<=10$ and xi is integer