(질문)
12865호: 일반 백팩
첫 번째 줄은 항목 수 N(1≤N≤100)과 기준이 견딜 수 있는 가중치 K(1≤K≤100000)를 제공합니다.
두 번째 라인부터 N라인까지는 각 오브젝트의 가중치 W(1≤W≤100000)와 오브젝트 V의 값(0≤V≤1000)
www.acmicpc.net
(문제를 풀다)
이것은 배낭 문제의 전형적인 예입니다.
DP 스터디가 부족해서 영상을 보고 스터디 냅색을 참고했습니다.
영상에도 나오는데 중요한건 dp(백팩 개수)(무게)
//cost는 해당 배낭의 무게 value는 해당 배낭의 가치이다.
dp(배낭2)(무게) = max(dp(배낭2 - 1)(무게), dp(배낭2 - 1)(무게 - cost(배낭2)) + value(배낭2)이 코드를 사용하여 마지막 배낭의 최대 무게가 총 얼마인지 확인할 수 있습니다.
(검토)
1. 워낙 유명한데 깊이 파고들지 않아서 처음 봤을 때 익숙한 듯하면서도 이해하기 어려웠다.
2. 처음에는 욕심 문제인 줄 알고 친해졌는데 아닌 걸 보니 원한 건가 싶었는데 아무리 봐도 원한 건 아니었다.
3. 문제를 풀고 나니 체감이 되지만 코딩 테스트에 사용된 알고리즘에 여러 문제가 있었던 기억이 납니다.
일을 끝내고 가자.
(암호)
#include <iostream>
#include <algorithm>
using namespace std;
int dp(101)(100001);
int cost(101);
int value(101);
int n,k;
int main(){
cin>>n>>k;
for(int i = 1;i<=n;i++){
cin>>cost(i)>>value(i);
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=k;j++){
if(j - cost(i) >= 0){
dp(i)(j) = max(dp(i - 1)(j - cost(i)) + value(i), dp(i - 1)(j));
}
else{
dp(i)(j) = dp(i - 1)(j);
}
}
}
cout<<dp(n)(k)<<endl;
return 0;
}