C++ Knapsack DP
Use a dp vector to store every possible value which can be formed from the topping. For each base, we search from the target to get the closest value. Notice th
Use a dp vector to store every possible value which can be formed from the topping. For each base, we search from the target to get the closest value. Notice that we should search the lower value first. \n\n```\nclass Solution {\npublic:\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        int sum = accumulate(toppingCosts.begin(), toppingCosts.end(), 0) * 2;\n        int dp[sum + 1];\n        for(int i = 0; i <= sum; ++i)\n            dp[i] = 0;\n        dp[0] = 1;\n        for(int i = 0; i < toppingCosts.size(); ++i) {\n            for(int j = sum; j >= 0; --j) {\n                if(j - toppingCosts[i] >= 0 && dp[j - toppingCosts[i]] == 1)\n                    dp[j] = 1;\n                else if(j - 2 * toppingCosts[i] >= 0 && dp[j - 2 * toppingCosts[i]] == 1)\n                    dp[j] = 1;\n            }\n        }\n    \n        int result = INT_MAX;\n        for(int i = 0; i < baseCosts.size(); ++i) {\n            int dif = 0; \n            if(target - baseCosts[i] <= 0) {\n                if(baseCosts[i] - target < abs(result - target))\n                    result = baseCosts[i];\n                continue;\n            }\n            while(target - baseCosts[i] - dif >= 0 || target - baseCosts[i] + dif <= sum) {\n                if(target - baseCosts[i] - dif >= 0 && dp[target - baseCosts[i] - dif] == 1) {\n                    if(dif <= abs(target - result)) {\n                        result = target - dif;\n                        break;\n                    }        \n                }\n                \n                if(target - baseCosts[i] + dif <= sum && dp[target - baseCosts[i] + dif] == 1) {\n                    if(dif < abs(target - result)) {\n                        result = target + dif;\n                        break;\n                    }        \n                }\n                ++dif;\n            }\n        }\n        return result;\n    }\n};\n```
['Dynamic Programming', 'C']