일단 주석 달아봤습니나
#include
#include
using namespace std;
//12865 평범한 배낭
int n,k;
int w[101],v[101];// 무게배열 가치배열
int arr[101][100001];
/*
특정 물건이 들어가는지를 확인하기 위해 쓰이는 배열입니다
일단 접근 방식은 이렇습니다
----------------------
정말 평범한 샙낵? 백색? 냅색? 문제다
근데 문제를 풀며 느낀 문제는 내가 접근한 방법이 맞냐는 거다…..
일단 내 접근 방법을 설명하자면….
자, 예를 들어 3키로만큼 들 수 있고,
1키로에 가치 1
1킬로에 가치1 한개더
1키로에 가치 2
2키로에 가치 2
3키로에 가치 1 이렇게 있다고 가정해보자
나는 일단 1킬로일때 들 수 있는 경우를 생각했다
1킬로에 가치1을 들면 1가치
1킬로에 가치2를들면 2가치
안들면 그냥 0가치다
이렇게 1킬로를 들 수 있는 경우에는 최대 2가치를 들 수 있다.
그리고 이 가치를 다이나믹하게 다이나믹한 곳에 저장을 해두자
그런데!! 만약 2킬로를 들 수 있다면?
그냥 무지성으로 넣어보는 경우도 있지만
우리에겐 다이나믹하게 쓰이기 위해 다이나믹한 곳에 다이나믹하게 저장해둔 다이나믹한 값이 있다!
그러면 다이나믹하게 1킬로를 들 때의 최대값에 다른 1킬로짜리를 하나 넣을 수 있다
아니면 2키로짜리 하나 드던가…
어쨋거나 이렇게 두가지 경우중에 큰 값을 다이나믹 어쩌구 저장해두자!
자 다음단계! 대망의 3킬로를 들 수 있다 가정하는 단계이다! 우리에겐 다이나믹 어쩌구 한 1키로 최대값과 2키로 최대값이 있다!
아무튼 그래서 경우의 수는
1킬로의 최대값 + 2키로짜리
2킬로의 최대값 + 1킬로따리
그냥 3킬로짜리
이렇게중에 최대값을 고르면 된다!
-----------------------
저런 방식으로 접근했을때
2킬로의 최대값에는 1킬로에 가치2와 1킬로의 가치1 이 하나씩 쓰였다
1킬로에 가치2은 첫번째(입력 들어온 순서)고
1킬로애 가치1은 두번째다.(j라고 가정하자)
그리고 이 둘은 2(i라고 가정하자)킬로일때의 최대값에 쓰인다.
그러면 arr[j][i]에 1을 기록한다(초기값은 0이다)
이 경우에는 arr[1][2]랑 [2][2]가 기록될 것이다.
그리고 나중에 3킬로의 최대를 구해야 될 때가 되면
1킬로에 가치1(앞에 쓰인거 말고 3번째 물건임)을 2킬로일때의 최대값에다
더해준다.
그렇게 3킬로일때의 최대값을 구할 수 있다
그런데 3킬로 일때는 최대1킬로일때의 최대값에 2킬로에 가치2(4번째꺼)를 더해서도 구할 수 있고
그냥 3킬로에 가치2(5번째꺼)일수도 있다
이렇게 3가지의 경우중에 제일 첫번째 경우가 최대값이다
그러면 최대3킬로일때 가치 최대합을 구할때 구성된 애들을 arr에 기록해야 한다
최대 3킬로일때니 arr[?][3]에다 기록할거다
근데 이때 최대 2킬로일때 가치최대합을 이용해서 했으니까
최대 2킬로일때 가치 최대합 arr ? 2의 값을 arr ? 3에다 복사한 다음
1키로에 가치1(3번째꺼)가 쓰엿다고 표시하면 된다
arr3(3번째 물건이다)3(3의 최대값이다)에다 1을적자
그렇게 반복을 하면 된다
이렇게 보니까 설명 겁나기네
*/
int dy[100001];
int pack(int size_) {
if(size_==0) return 0;
//최대 0키로 들수있을때 최대는 당연히 0이겠지
if(dy[size_]!=-1) {
return dy[size_];
//size_일때 얼마 들 수 있는지 기록해 뒀다면 그거를 쓰자
}
int max=pack(size_-1);
/*이러는 이유는 그 뭐드라
만약에 사이즈가 5인데 물건들이 하나는 1키로고 나머지는 다 5키로가 넘으면
최대값은 1킬로따리를 넣은거일거다
이런 경우에는 사이즈-1을 그 넣어서 구한다
*/
int d=1;
int maxi,maxj;
int temp=0;
// printf("size %d",size_);
for(int j=0;j
sasak2 1년 전
네....
질문글에 있는거 다 해봤는데도 안되네여
ㅠㅠ