제민
DP [Knapsack](1) - 평범한 배낭, 앱, 안녕, 최대 페이지 수, 양팔저울 본문
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;
}
'코테연습일지 > DP' 카테고리의 다른 글
DP(5) 팰린드롬?, 암호코드 (0) | 2024.02.18 |
---|---|
9084 2293 2294 동전 (0) | 2024.02.18 |
DP(4) - 카드 구매하기, 오르막 수, 스티커 (0) | 2024.02.16 |
DP(3) - 부분 수열, 퇴사, 쉬운 계단 수 (0) | 2024.02.15 |
DP(2) - 피보나치 함수, 정수 삼각형, 이친수 등... (0) | 2024.02.14 |