[동적 기획] 1차원 가방과 2차원 가방 템플릿 문제 NOIP2005 보급팀 채약+luogu P1855 착취kksc03
1721 단어 동적 기획
대략적인 제목 묘사: 동굴 안에는 서로 다른 약초가 있는데 한 그루씩 따는 데 시간이 좀 걸리고 한 그루마다 그 자체의 가치가 있다.자네에게 시간을 주겠네. 그 동안 약초를 채집할 수 있을 거야.채집한 약초의 총가치를 가장 높인다.
입력 형식:
첫 줄에는 2개의 정수 T(1≤T≤1000)와 M(1≤M≤100)이 있는데 한 칸으로 칸막이를 하면 T는 모두 약초를 채취할 수 있는 시간, M은 동굴 안의 약초의 수를 나타낸다.다음 M행은 줄마다 1에서 100 사이(1과 100 포함)의 정수 a와 b 두 개를 포함하여 각각 어떤 약초를 따는 시간과 이 약초의 가치를 나타낸다.
출력 형식:
1개의 정수는 정해진 시간 안에 채취할 수 있는 약초의 최대 총가치를 나타낸다.
현재의 약초를 고르든지 말든지 따다
먼저 모든 채약을 매거한 다음에 매거 시간[출처를 찾는 데 중점을 두기 때문에 거꾸로 해야 한다. 그리고 모든 약초는 하나밖에 없다. 만약에 매거를 하고 있어서 이 점을 확정하지 못하면 자신이 남긴 흔적의 영향을 찾아낼 수 있다. 예: 매거를 하고 있으면 a=2, (b는 중요하지 않다) 매거를 s[1](s는 dp수조)로 표시할 때 s[2]를 표시한다.그러나 s[2]를 일일이 들었을 때 표시를 한다] 선택할 때: 이전 상태 s[j-a] 보존 최대치 + 현재 일일이 들었던 약초의 가치 > 현재 상태 보존 최대치 (반대로 선택하지 않는다)
#include
using namespace std;
int s[1500] = {}; // ,
int main()
{
int n, m;
int i, j;
int a, b;
cin >> n >> m;
for (i = 1; i <= m; i++)
{
cin >> a >> b;
for (j = n; j >= a; j--)
s[j] = max(s[j], s[j - a] + b);
}
cout << s[n] << endl;
return 0;
} 2D 가방
구체적인 매거 과정은 1차원 배낭과 매우 비슷하며, 선택하거나 선택하지 않는 것은 매거 배낭 용량을 선택할 때 이중 순환(2차원)이다.
예: 로곡P1855kksc03 착취https://www.luogu.org/problemnew/show/P1855
#include
using namespace std;
int s[220][220];
int main()
{
int n, m, t;
int i, j, k;
int a, b;
cin >> n >> m >> t;
memset(s, 0, sizeof(s));
for (i = 1; i <= n; i++)
{
cin >> a >> b; // ，
for (j = m; j >= a; j--)
for (k = t; k >= b; k--)
s[j][k] = max(s[j - a][k - b] + 1, s[j][k]);
}
cout << s[m][t] << endl;
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
