제민

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

코테연습일지/DP

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

jemin0619 2024. 2. 16. 23:34

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

더보기
#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번: 앱

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활

www.acmicpc.net

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번: 안녕

첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번

www.acmicpc.net

오래간만에 자력솔을 해냈다... 체력을 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번: 최대 페이지 수

첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이

www.acmicpc.net

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

더보기
#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번: 양팔저울

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무

www.acmicpc.net

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;
}