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

傷城~ 2023-01-17 08:28 119阅读 0赞

（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;
        }
    };