약 을 따다

1547 단어 알고리즘
설명 설명  천진 은 타고 난 자질 이 총명 한 아이 로 그의 꿈 은 세계 에서 가장 위대 한 의사 가 되 는 것 이다.이 를 위해, 그 는 부근 에서 가장 명망 있 는 의 사 를 스승 으로 모 시 려 고 한다.의 사 는 그의 자질 을 판단 하기 위해 그 에 게 어 려 운 문 제 를 냈 다.의 사 는 그 를 약초 가 가득 한 동굴 로 데 리 고 가서 그 에 게 말 했다."얘 야, 이 동굴 에 다른 약초 들 이 있어. 한 포기 한 포기 따 는 데 시간 이 걸 리 고, 한 포기 에 도 가치 가 있어. 내 가 시간 을 줄 게. 그 동안 약 초 를 캐 도 돼. 똑똑 한 아이 라면 약초 의 총가치 가 가장 클 거 야."만약 당신 이 진진 이 라면, 당신 은 이 임 무 를 완성 할 수 있 습 니까?
입력 형식 입력 형식 
첫 줄 은 두 개의 정수 T (1 & lt; T & gt; = 1000) 와 M (1 & gt; = M & gt; = 100) 로 나 뉘 어 져 있 으 며, T 는 모두 약 초 를 채취 할 수 있 는 시간 을 의미 하 며, M 은 동굴 안의 약초 의 수 를 나타 낸다. 다음 M 행 은 각각 1 ~ 100 사이 (1 과 100 포함) 의 정 수 를 포함 하여 어떤 약 초 를 채취 하 는 시간 과 이 약초 의 가 치 를 나타 낸다.
출력 형식 출력 형식
한 줄 을 포함 하여 이 줄 은 정 해진 시간 내 에 채취 할 수 있 는 약초 의 최대 총 가 치 를 나타 내 는 정수 만 포함 하고 있 습 니 다.
출력
시간: 1 초
/**
	    : 
	           ,           
	      
	      ,         。
	                 。
	
	    :
	01     
*/
 
 #include 
 #include 
 using namespace std;
 #define mNum 101
 int time[mNum];
 int value[mNum];
 int best[mNum][mNum];				//best[i][j]:   i    j           

 int main()
 {
 	int t,m;
 	cin>>t>>m;						//    ,    
	for(int i=1;i<=m;i++)
	{
		cin>>time[i]>>value[i];
	}
	
	memset(best,0,sizeof(best));	//      
	
	for(int i=1;i<=m;i++)			//m    
	{
		for(int j=1;j<=t;j++)		//   
		{
			best[i][j] = best[i-1][j];
			if(j>=time[i])
				best[i][j] = max(best[i-1][j],best[i-1][j-time[i]]+value[i]);
		}
	}
	
	cout<

좋은 웹페이지 즐겨찾기