poj 2063 투자 -- 완전 가방
d 가지 주식 이 있 습 니 다. 모든 주식 은 구 매 금액 과 수익 이 있 습 니 다. 원금 C 가 있 습 니 다. year 년 후에 가장 큰 투자 수익 을 얻 을 수 있 는 것 은 얼마 입 니까?
분석:
그러면 여기 서 우 리 는 모든 주식 을 무한 회 구 매 할 수 있다 는 것 을 알 수 있다. 그러면 여기 서 완전한 가방 문제 임 을 알 수 있 고 원금 C 를 가방 으로 볼 수 있다.근 데 처리 가 필요 해 요.
우 리 는 단독으로 1 년 의 수익 을 보고 dp 과정 을 분석 합 니 다.
dp [i] [j] 는 제 i 종 주식 을 고려 하여 j 가 이렇게 많은 돈 을 사용 할 때의 최대 수익 을 고려한다 고 밝 혔 다.이전의 백화 가방 의 완전한 가방 을 통 해 우 리 는 이곳 이 1 차원 배열 로 최적화 되 었 다 는 것 을 알 수 있다.
그러나 dp 배열 이 너무 크 지 않 고 주식 가격 이 1000 의 배수 라 는 점 을 감안 하여 우리 가 처리 해 야 할 것 은 여기 서 매번 금액 을 1000 으로 나 누 는 것 이다.
또한, 매년, 우 리 는 완전히 가방 을 한 번 에 최대 이익 을 얻 은 후에 모든 금액 을 다음 해 에 완전히 가방 에 드 립 니 다.
말 에 오르다
//
#include <stdio.h>
#include <string.h>
#define MAX 50005
int N;//
int d;//
int V[11],In[11];//
int ans[MAX];//dp
int dp(int pre)
{
memset(ans,0,sizeof(ans));
for(int i = 1; i <= d; i ++)
{
for(int j = V[i]; j <= pre; j ++)
{
ans[j] = ans[j]>ans[j-V[i]]+In[i] ? ans[j]:ans[j-V[i]]+In[i];
}
}
return ans[pre];
}
int main()
{
int C,year;//
scanf("%d",&N);
while(N--)
{
scanf("%d%d%d",&C,&year,&d);
for(int i = 1; i <= d; i ++)
{
scanf("%d%d",&V[i],&In[i]);
V[i] /= 1000;
}
for(int i = 1; i <= year; i ++) //
{
C += dp(C/1000);
}
printf("%d
",C);
}
return 0;
}
/*
1
10000 4
2
4000 400
3000 250
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
