C++ | DP Similar to Knapsack O(m * 20000)
Uses similar idea to 0/1 knapsack dp solution.\nThe code are basically self explainatory.\n\n\nclass Solution {\npublic:\n    int closestCost(vector<int>& baseC
Uses similar idea to 0/1 knapsack dp solution.\nThe code are basically self explainatory.\n\n```\nclass Solution {\npublic:\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        vector<bool> possible(20010, false);\n        for(auto b : baseCosts)\n            possible[b] = true;\n        \n        for(auto t : toppingCosts) {\n            for(int _ = 0; _ < 2; _++) // at most two of each type\n            for(int i = 20005-t; i >= 1; i--) {\n                if(possible[i])\n                    possible[i+t] = true;\n            }\n        }\n        \n        int closest = 20010, ans;\n        for(int i = 1; i < 20010; i++) {\n            if(possible[i] && abs(target-i) < closest) {\n                closest = abs(target-i);\n                ans = i;\n            }\n        }\n        \n        return ans;\n    }\n};\n```
[]