DP [Knapsack](1) - 평범한 배낭, 앱, 안녕, 최대 페이지 수, 양팔저울

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

#include <bits/stdc++.h>
using namespace std;
int w[105],v[105],d[105][100005];

//D[i][j]란
//처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최댓값 

int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int n,k; cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){ //무게 
			//배낭에 넣을 수 있다면 넣었을 때와 넣지 않았을 때 중 최댓값을 취함
			if(j-w[i]>=0) d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+v[i]);
			//못넣은다면 넣지 않았을 때 값을 취함 
			else d[i][j]=d[i-1][j];
		}
	}
	cout<<d[n][k];
	return 0;
}

D[i][j]는 i번째 물건까지 살펴보고 배낭의 용량이 j일때 배낭에 들어간 가치의 최댓값이다.

 

6 13

4 8

3 6

5 12

각 물건의 무게와 가치이다. 배낭의 용량은 7로 한다.

먼처 첫 번째 물건만 고려했을 때 D[1]을 살펴보자.

D[1] = {0, 0, 0, 0, 0, 0, 13, 13}

D[2] = {0, 0, 0, 0, 8, 8, 13, 13}

D[3] = {....}

....

1. 이전에 탐색했을 때의 현재 물건을 넣지 않았을 때의 가치 최댓값에 현재 물건의 가치를 더한 값

2. 이전에 탐색했을 때 최댓값

 

둘 중 더 큰 값을 d[i][j]에 넣는다. 그러면 d[n][k]에 답이 저장되어 있을 것이다.

---

 

https://www.acmicpc.net/problem/7579

7579번: 앱

Knapsack 알고리즘으로는 배낭에 가장 많이 넣을 수 있는 경우를 구하기에 D의 정의를 최소~~로 하면 안된다. 이 점을 모르고 풀어서 많이 힘들었다. 

D를 얻을 수 있는 최대 메모리 크기로 설정해 D가 필요한 메모리 크기 이상일 경우 res를 갱신하도록 했다.

#include <bits/stdc++.h>
using namespace std;
int d[103][10003]; //i번째 앱까지 확인했고 얻은 메모리가 j의 비용으로 얻을 수 있는 최대 메모리 크기
int M[103],C[103]; //M_i는 i번째 앱에서 얻는 메모리, C_i는 i번째 앱에서 사용되는 비용
int res=0x7f7f7f7f,sum=0;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>M[i];
    for(int i=1;i<=n;i++) {cin>>C[i]; sum+=C[i];}
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sum;j++){ //cost는 0~sum까지 있음
            if(j-C[i]>=0) d[i][j]=max(d[i-1][j],d[i-1][j-C[i]]+M[i]);
            else d[i][j]=d[i-1][j];
            if(d[i][j]>=m) res=min(res,j);
        }
    }
    cout<<res;
    return 0;
}

//배낭 알고리즘은 최대 크기를 구하기에 최대 메모리 크기를 구하는 방식으로 가야 한다.

---

https://www.acmicpc.net/problem/1535

1535번: 안녕

오래간만에 자력솔을 해냈다... 체력을 100 사용하면 죽기에 최대 99까지 가게 했다.

#include <bits/stdc++.h>
using namespace std;
int d[103][103]; //i번 사람까지 탐색했고 사용한 체력이 j일때 얻을 수 있는 최대 행복
int h[103],hp[103];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,mx=0; cin>>n;
    for(int i=1;i<=n;i++) cin>>hp[i];
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=99;j++){
            if(j-hp[i]>=0) d[i][j]=max(d[i-1][j],d[i-1][j-hp[i]]+h[i]);
            else d[i][j]=d[i-1][j];
            mx=max(mx,d[i][j]);
        }
    }
    cout<<mx;
    return 0;
}

---

https://www.acmicpc.net/problem/16493

16493번: 최대 페이지 수

이 문제도 실버여서 자력솔을 해보았다. 생각보다 할만했다. 다 비슷한 코드를 사용해서 어렵지 않다.

#include <bits/stdc++.h>
using namespace std;
int d[23][203]; //i챕터까지 탐색했을 때 남은 기간 j일 동안 읽을 수 있는 최대 페이지 수
int day[23]; //챕터당 소요되는 일 수
int page[23]; //챕터당 페이지 수
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int N,M; cin>>N>>M;
    for(int i=1;i<=M;i++){
        cin>>day[i]>>page[i];
    }
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            if(j-day[i]>=0) d[i][j]=max(d[i-1][j],d[i-1][j-day[i]]+page[i]);
            else d[i][j]=d[i-1][j];
        }
    }
    cout<<d[M][N];
    return 0;
}

---

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

DFS로 풀긴 했는데 DP와 DFS의 경계가 확실하게 있는건지 모르겠다.

dp[i][j] = i번째 추까지 고려했을 때 j를 측정할 수 있는가?1. 현재 추를 선택함2. 추를 선택하지 않음3. 추를 내려놓음

#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[33]; //나온 무게들 저장할 idx
int vis[33][40003];

void dfs(int cnt,int weight){
    if(cnt>n) return;
    if(vis[cnt][weight]) return;
    vis[cnt][weight]=true;
    dfs(cnt+1,weight+a[cnt]);
    dfs(cnt+1,weight);
    dfs(cnt+1,abs(weight-a[cnt]));
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    memset(vis,false,sizeof(vis));
    cin>>n; //추의 갯수
    for(int i=0;i<n;i++) cin>>a[i];

    dfs(0,0);

    cin>>k;
    while(k--){
        int temp; cin>>temp;
        if(vis[n][temp]) cout<<"Y ";
        else cout<<"N ";
    }
    return 0;
}