DFS（贪心问题）--解决最少数量装箱问题

题目描述

有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）

需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

输入描述:

输入箱子载重量X(1 <= X <= 10000)，一个整数。

输出描述:

如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。

示例1

输入

复制

4

输出

复制

-1

说明

无法装满

示例2

输入

复制

8

输出

复制

2

#include<iostream>
#include<vector>
using namespace std;
/*    全局变量    */
 
bool Flag = true;
vector<vector<int>> Result;
 
void DFS(vector<int>& Vec,int target,int val){
    Vec.push_back(val);
    if(target == val){
        Result.push_back(Vec);
        Flag = false;
    }
    if(target - val >= 7 && Flag){
        DFS(Vec,target - val,7);
    }
    if(target - val >= 5 && Flag){
        DFS(Vec,target - val,5);
    }
    if(target - val >= 3 && Flag){
        DFS(Vec,target - val,3);
    }
    Vec.pop_back();
}
 
int main(){
    int X;
    cin >> X;
    vector<int> Vec;
    DFS(Vec,X,7);
    DFS(Vec,X,5);
    DFS(Vec,X,3);
    if(Result.size() == 0){
        cout << "-1" << endl;
    }
    else{
        cout << Result[0].size() << endl;
    }
    return 0;
}

心得：这道题涉及贪心算法+DFS+减枝