You are given a list AA positive integers a1,,ana1,,an, and a positive integer BB. A subset S{1,2,,n}S{1,2,,n} is called feasible if its weight doen't exceed BB, i.e., if

iSaiB.iSaiB.

Your goal is to find a feasible subset S{1,2,,n}S{1,2,,n} such that

iSaiM/2,iSaiM/2,

where MM is the maximum weight achievable by any feasible subset.

Give an algorithm to solve this problem in time O(n)O(n).

Q4 (10 points) You are given a list A positive integers a1, ..., An, and a positive integer B. A subset S C{1,2,...,n} is called feasible if its weight doen't exceed B, i.e., if M/2, ies where M is the maximum weight achievable by any feasible subset. Give an algorithm to solve this problem in time O(n). Q4 (10 points) You are given a list A positive integers a1, ..., An, and a positive integer B. A subset S C{1,2,...,n} is called feasible if its weight doen't exceed B, i.e., if M/2, ies where M is the maximum weight achievable by any feasible subset. Give an algorithm to solve this problem in time O(n)