Closest Dessert Cost（C++最接近目标價格的甜點成本）

（1）01背包

class Solution {
public:
    int gap=INT_MAX;
    int tag=0;
    int ops=0;
    void helper(vector<int>& toppingCosts, int target,int a) {
        if(abs(a-target)<gap) {
            tag=a;
            gap=abs(tag-target);
            if(tag-target>=0) ops=1;
            else ops=0;
        } else if(abs(a-target)==gap) {
            if(a-target<0 && ops==1) {
                tag=a;
                ops=0;
            }

        }
       
        int n=toppingCosts.size();
        vector<vector<int>> v(n+1,vector<int>(11000+1,0));
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=11000;j++) {
                if(j<toppingCosts[i-1]) v[i][j]=v[i-1][j];
                else v[i][j]=max(v[i-1][j],v[i-1][j-toppingCosts[i-1]]+toppingCosts[i-1]);
                if(abs(v[i][j]+a-target)<gap) {
                    tag=v[i][j]+a;
                    gap=abs(tag-target);
                    if(tag-target>=0) ops=1;
                    else ops=0;
                } else if(abs(v[i][j]+a-target)==gap) {
                    if(v[i][j]+a-target<0 && ops==1) {
                        tag=v[i][j]+a;
                        ops=0;
                    }
                    
                }
                    
            }
        }
        return;
    }
    
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int n=toppingCosts.size();
        for(int i=0;i<n;i++) {
            toppingCosts.push_back(toppingCosts[i]);
        }
        
        for(int i=0;i<baseCosts.size();i++) {
            helper(toppingCosts, target, baseCosts[i]);
        }
        return tag;
    }
};