3510 : 예산 관리

문제

예산 관리

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int>v;
int B,N,ans;

void backtracking(int sum,int index){
    if(sum>B) return;
    ans= max(ans,sum);
    for(int i=index+1; i<N; i++){
        if(sum+v[i]>B) continue;
        backtracking(sum+v[i], i);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>B;
    cin>>N;
    
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    
    sort(v.begin(),v.end(),greater<>());
    for(int i=0; i<N; i++){
        backtracking(v[i], i);
    }
   
    cout<<ans;
}

 

풀이

처음에 냅색 문제인가 싶었지만 N이 21밖에 되지 않아서 백트랙킹으로 해결했습니다.