题目

https://leetcode-cn.com/problems/shopping-offers/

大礼包.png

代码

class Solution {
public:
    int min;
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        min=calsingle(price,needs,0);
        search(price,special,needs,0);
        return min;
    }
    void search(vector<int>& price, vector<vector<int>>& special, vector<int>& needs,int current){
        for(int i=0;i<special.size();i++){//1 for范围，每个礼包都可选
            //2 条件 A礼包中每个物品小于需求数
            if(pd(i,special,needs)){
                select(i,special,needs);//选上
                current+=special[i].back();//当前总价把这个礼包价格加上
                int total=calsingle(price,needs,current);//计算补上单品后的总价
                if(total<min) min=total;//总价小则min=这个
                search(price,special,needs,current);//搜索下一层
                unselect(i,special,needs);//回溯，不选这个了
                current-=special[i].back();//当前总价把这个礼包价格减掉
            }
        }
    }
    /* 判断这个大礼包数量是否超过所需 */
    bool pd(int i ,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            if(special[i][m]>needs[m]) return false;
        }
        return true;
    }
    /* 选择i号礼包，从needs列表中减掉i 中每个产品数量*/
    void select(int i,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            needs[m]-=special[i][m];
        }
    }
    /* 回溯i号礼包，从needs列表中加上i中每个产品数量*/
    void unselect(int i,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            needs[m]+=special[i][m];
        }
    }
    /* 计算剩余needs列表全按单品购买的价格 */
    int calsingle(vector<int>& price,vector<int>& needs,int current){
        int sum=0;
        for(int m=0;m<needs.size();m++){
            sum+=needs[m]*price[m];
        }
        return sum+current;
    }
};

简析

这个题挺有意思的，从搜索回溯的角度想，按如下步骤思考

• A for循环范围
• B 判断是否可选
• C 选择后的相关变量变化
• D 回溯
• E 最优解与结束条件等

通过此题能学到什么

• 对于复杂题目，一定要封装一些小函数，这样主代码逻辑清晰，也易于修改与测试。
• special[i].back(); 此处back()是向量中自带的函数，得到向量的最后一个数。

A for循环范围

礼包不止能买一个，所以所有礼包都可以选，for循环范围即为礼包向量的长度。

 for(int i=0;i<special.size();i++){//1 for范围，每个礼包都可选

B 判断

判断即判断选上这个礼包后，是否超出购买个数。比如这个礼包有2个A，你还需要一个，这个就不能选。

/* 判断这个大礼包数量是否超过所需 */
    bool pd(int i ,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            if(special[i][m]>needs[m]) return false;
        }
        return true;
    }

C 选择后

选上后，将需求清单相应物品数量减少，总价加上礼包数

select(i,special,needs);//选上
current+=special[i].back();//当前总价把这个礼包价格加上

    /* 选择i号礼包，从needs列表中减掉i 中每个产品数量*/
    void select(int i,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            needs[m]-=special[i][m];
        }
    }

D 回溯，和选择正相反

 /* 回溯i号礼包，从needs列表中加上i中每个产品数量*/
    void unselect(int i,vector<vector<int>>& special, vector<int>& needs){
        for(int m=0;m<needs.size();m++){
            needs[m]+=special[i][m];
        }
    }

其他

目前为止，还缺点东西，怎么结束和得出最终结果。我们每选一个礼包后，剩下的需求清单中的物品都用单独购买凑一下，如果凑齐后的总价小于当前保存的最低价，最低价等于这个数。

int total=calsingle(price,needs,current);//计算补上单品后的总价
if(total<min) min=total;//总价小则min=这个

 /* 计算剩余needs列表全按单品购买的价格 */
    int calsingle(vector<int>& price,vector<int>& needs,int current){
        int sum=0;
        for(int m=0;m<needs.size();m++){
            sum+=needs[m]*price[m];
        }
        return sum+current;
    }