[DP 가방 문제 1] noi openjudge 2.6 채약
5016 단어 DP
1775:약초 채취
총 시간 제한:
1000ms
메모리 제한:
65536kB
묘사
천진은 매우 잠재력이 있고 타고난 자질이 총명한 아이로 그의 꿈은 세계에서 가장 위대한 의사라고 불리는 것이다.그래서 그는 근처에서 가장 명망이 높은 의사를 스승으로 모시고 싶었다.의사는 그의 자질을 판단하기 위해 그에게 어려운 문제를 하나 냈다.의사는 그를 약초가 널려 있는 동굴로 데리고 가서 말했다. "얘야, 이 동굴에는 다른 약초가 있어. 한 그루씩 따는 데 시간이 좀 걸릴 거야. 한 그루마다 가치가 있어. 내가 시간을 줄게. 그 동안 약초를 따도 돼. 똑똑한 아이라면 채취한 약초의 총 가치가 가장 클 거야."
만약 네가 진진이라면, 너는 이 임무를 완성할 수 있니?
입력
입력한 첫 줄에는 두 개의 정수 T(1<=T<=1000)와 M(1<=M<=100)이 있는데, T는 모두 약초를 채취할 수 있는 시간을 대표하고, M은 동굴 속의 약초의 수를 대표한다.다음 M행은 줄마다 1에서 100 사이(1과 100 포함)의 정수 두 개를 포함하여 각각 어떤 약초를 따는 시간과 이 약초의 가치를 나타낸다.
출력
수출은 한 줄만 포함하고 이 줄은 한 정수만 포함하며 규정된 시간 안에 채취할 수 있는 약초의 최대 총가치를 나타낸다.
샘플 입력
70 3
71 100
69 1
1 2
샘플 출력
3
분석:
비할 바 없이 고전적인 가방 문제 01, f[v]로 v 단위 시간 획득할 수 있는 최대 가치를 표시하고,
w[i]는 시간, c[i]는 가치, 모든 물품에 대한 선택, 선택하지 않음
선택하지 않음: f[v]=f[v];
선택: f[v]=f[v-w[i]]+c[i];(v>=w[i])
상태 전이 방정식은 다음과 같다. f[v]=max(f[v], f[v-w[i]]+c[i]).
코드는 다음과 같습니다.
#include이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
