개발자 톡
동적 계획법 (dp)로 푸는 방법 없을까요?
- 등록일
- 2024-03-20 18:49:55
- 조회수
- 315
- 작성자
- yeinseo1142
일반적인 배낭 문제처럼 풀고 싶은데 잘 안되네요ㅜㅜ 같이 고민해주시면 감사하겠습니다ㅜㅜ
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int main(void) {
int W, N;
scanf("%d %d", &W, &N);
int M[N], P[N];
for (int i = 0; i < N; i++) {
scanf("%d %d", &M[i], &P[i]);
}
int dp[N + 1][W + 1];
int decide=0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (M[i - 1] <= j) {
dp[i][j] = max(M[i-1]*P[i - 1] + dp[i - 1][j - M[i - 1]], dp[i - 1][j]);
if(decide!=M[i]) {decide=decide+M[i];}
// printf("%d\n",M[i]);}
// printf("%d\n", decide);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
int first=0;
int W2;
if (decide<W){
W2=W-decide;
int dp2[N+1][W2+1];
for (int i=0;i<N;i++){
for (int j = 0; j < W2+1; j++) {
if ( j == 0||i==0) {
dp2[i][j] = 0;
//printf("%d\n", dp2[i][j]);
}
else if ((M[i - 1] >= j)) {
dp2[i][j] = max(W2*P[i - 1] + dp2[i - 1][j - W2], dp2[i - 1][j]);
//decide=decide+M[i-1]
//printf("%d %d\n", j,dp2[i][j]);
}
else if (M[i - 1] < j){
dp2[i][j] = dp2[i-1][j];
}
else dp2[i][j] = dp2[i-1][j];
}
}
first=dp2[N-1][W2];
}
//printf("%d\n", decide);
//printf("%d\n", dp[N][W]);
//printf("%d\n", first);
printf("%d\n", first+dp[N][W]);
return 0;
}