백준 12865 : 평범한 배낭

문제

백준 12865 : 평범한 배낭

재귀로 풀기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,K;
int value_sum;
int weight_sum;
vector<pair<int,int>> v;//weight,value
vector<int> index_v;
vector<int> sum_v;
void function1(int push_index){
    //weight_sum 구하기
    //cout<<"function("<<push_index<<")\n";
    weight_sum=0;
    value_sum=0;
    for(int index:index_v){
        value_sum+=v[index].second;
        weight_sum+=v[index].first;
    }
    
    if(weight_sum+v[push_index].first>K){
        
        // for(int index : index_v){
        //     cout<<index<<" ";
        // }

        //cout<<"\n";
        //cout<<"value_sum : "<<value_sum<<"\n";
        
        //sum_v에 value_sum push_back하기
        sum_v.push_back(value_sum);
        //index_v pop하기
        //index_v.pop_back();
        //value_sum , weight_sum 초기화
        value_sum=0; 
        weight_sum=0;
        //cout<<"return\n";
        return;
    }
    
    
        
    index_v.push_back(push_index);
    for(int i=push_index+1;i<N;i++){
        function1(i);
    }
    index_v.pop_back();
    
    
}
int main(){
    
    cin>>N>>K;
    for(int i=0;i<N;i++){
        int W,V;
        cin>>W>>V;
        v.push_back({W,V});
    }
    sort(v.begin(),v.end());

    
    for(int s=0;s<N;s++){
        //cout<<"main>for>before\n";
        function1(s);
        //cout<<"main>for>after\n";
        
    }
    
    // for(int a:sum_v){
    //     cout<<a<<" ";
    // }
    //cout<<"\n";
    auto max_iter = max_element(sum_v.begin(), sum_v.end());
    cout << *max_iter << endl;


}

DP로 풀기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,K;
vector<pair<int,int>> v;//weight,value
int DP[101][100001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int W,V;
    cin>>N>>K;
    v.push_back({0,0});
    for(int i=0;i<N;i++){
        cin>>W>>V;
        v.push_back({W,V});
    }
  
    

    for(int i=1;i<=N;i++){//i가 개수
        for(int j=1;j<=K;j++){//j가 weight
          
            int weight=v[i].first;
            int value=v[i].second;

            if(j-weight>=0)
                DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value);
            else 
                DP[i][j]=DP[i-1][j];
            
        }
    }
    
    // for(int i=0;i<N;i++){
    //     for(int j=0;j<=K;j++)
    //         cout<<DP[i][j]<<" ";
    //     cout<<"\n";
    // }
    
    cout<<DP[N][K];
    

}

트러블 슈팅

v.push_back({0,0});

DP[i][j]가 i=1,j=1부터 접근하므로
v[i]의 weight와 value를 i=1부터 접근할 수 있도록
처음에 v(백터)에 {0,0}을 push 해주어야 한다.