250x250
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- flutter network call
- 프로그래머스 알고리즘
- 막내의막무가내 코볼 COBOL
- 막내의막무가내 일상
- 막내의 막무가내
- 안드로이드 sunflower
- 막내의막무가내 프로그래밍
- 막내의막무가내 rxjava
- 막내의막무가내 목표 및 회고
- 주엽역 생활맥주
- 주택가 잠실새내
- 막내의막무가내 코틀린
- 막내의막무가내 플러터 flutter
- 막내의막무가내 안드로이드 코틀린
- 막내의막무가내 안드로이드
- 안드로이드 Sunflower 스터디
- 부스트코스에이스
- 막내의막무가내 플러터
- 안드로이드
- 부스트코스
- 막내의 막무가내 알고리즘
- 막내의막무가내 SQL
- 막내의막무가내 알고리즘
- 프래그먼트
- 막내의막무가내
- 막내의막무가내 안드로이드 에러 해결
- 2022년 6월 일상
- Fragment
- 막내의막무가내 코틀린 안드로이드
- 막무가내
Archives
- Today
- Total
막내의 막무가내 프로그래밍 & 일상
[알고리즘] 백준 12865 평범한 배낭 -dp- 본문
728x90
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
백준 동적계획법1 단계별 풀기 마지막 문제인 평범한 배낭 문제를 풀어보았습니다 ㅎㅎ
풀다가 도저히 모르겠어서 아래 사이트를 참고해서 풀이했습니다. (설명도 매우 잘되어있었습니다.!)
https://fbtmdwhd33.tistory.com/60
[백준,BOJ 12865] 평범한 배낭(JAVA 구현)
-내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제��
fbtmdwhd33.tistory.com
풀이는 다음과 같습니다.
[java[
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //물품의수
int K = sc.nextInt(); //준서가 버틸수 있는 무게
int[][] dp = new int[N + 1][K + 1]; //[물품인덱스][무게] = 최대가치
int[] w = new int[N + 1]; //무게
int[] v = new int[N + 1]; //가치
for (int i = 1; i <= N; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
for (int i = 1; i <= N; i++) { //아이템 순
for (int j = 1; j <= K; j++) { //버틸수있는 무게(j)
dp[i][j] = dp[i - 1][j];
if (j - w[i] >= 0) { //들어갈 수 있는 무게인 경우
//이전아이템까지의 최대가치 vs 현재아이템의 최대 가치 + 현재아이템의 남은 무게에서의 최대가치
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
System.out.println(dp[N][K]);
}
}
mtjin/algorithm_practice
알고리즘 문제풀이 연습. Contribute to mtjin/algorithm_practice development by creating an account on GitHub.
github.com
댓글과 공감은 큰 힘이 됩니다. 감사합니다!!
728x90
'알고리즘 > DP' 카테고리의 다른 글
[알고리즘] 백준 1003 피보나치 함수 -dp- (0) | 2020.10.31 |
---|---|
[알고리즘] 백준 2293 동전1 -dp- (0) | 2020.06.19 |
[알고리즘] 백준 1912 연속합 -dp- (0) | 2020.06.18 |
[알고리즘] 프로그래머스 땅따먹기 -연습문제- -dp- (0) | 2020.05.21 |
[알고리즘] 백준 9251 LCS -dp- 자바 코틀린 (0) | 2020.04.30 |
Comments