Same as KnapSack problem | DP | Java
\nclass Solution {\n    public int closestCost(int[] base, int[] top, int tar) {\n        int m=top.length,size=100000;\n        for(int i:base)\n            si
```\nclass Solution {\n    public int closestCost(int[] base, int[] top, int tar) {\n        int m=top.length,size=100000;\n        for(int i:base)\n            size=Math.min(size,i);\n        int min=100000;\n        for(int i:top)\n            min=Math.min(min,i);\n        size+=min;\n\t\t\n\t\t//minimum size for the dp\n        size=Math.max(size+1,2*tar+1);\n        boolean[][] dp=new boolean[m+1][size];\n\t\t\n\t\t//base case\n        for(int b:base){\n            if(b<size)\n                dp[0][b]=true;\n        }\n\t\t\n\t\t//Generating the rest of DP table\n        for(int i=1;i<=m;i++){\n            for(int j=1;j<size;j++){\n                if(dp[i-1][j]){\n                    dp[i][j]=true;\n\t\t\t\t\t\n\t\t\t\t\t//using one topping\n                    if(j+top[i-1]<size){\n                        dp[i][j+top[i-1]]=true;\n\t\t\t\t\t\t\n\t\t\t\t\t\t//using same topping again if possible\n                        if(j+2*top[i-1]<size)\n                            dp[i][j+2*top[i-1]]=true;\n                    }\n                }\n            }\n        }\n        if(dp[m][tar])\n            return tar;\n        int res=-1000000;\n\t\t\n\t\t//computing nearest possible answer to target\n        for(int i=tar-1;i>=0;i--){\n            if(dp[m][i]){\n                res=i;\n                break;\n            }\n        }\n        for(int i=tar+1;i<size;i++){\n            if(dp[m][i]){\n                res=(tar-res)<=(i-tar)?res:i;\n                break;\n            }\n        }\n        return res;\n    }\n}\n\n//fastest O(N^2) time and space complexities\n```
[]