미 친 채 약 (완전 가방 예제 상세 설명)

12707 단어 기초 산법 문제동적 계획알고리즘경험 공유
제목.
모든 약 초 는 무제 한 채집 할 수 있 으 며, 모든 약 초 는 채 약 시간, 약초 가치 에 대응 하여 일정한 채 약 시간 에 채취 한 약의 최대 총 가 치 는 얼마 입 니까?
입력 형식 입력 첫 줄 에는 두 개의 정수 가 있 는데 각각 약 초 를 채취 할 수 있 는 시간 t 와 동굴 안의 약 초 를 대표 하 는 수량 m 를 나타 낸다.2 번 부터 (m + 1) 줄 까지 줄 마다 두 개의 정수, (i + 1) 줄 의 정수 ai, bi 는 각각 i 번 째 약 초 를 따 는 시간 과 이 약 초 를 따 는 가 치 를 나타 낸다.
출력 형식 은 한 줄 을 출력 합 니 다. 이 줄 은 하나의 정수 만 포함 하고 정 해진 시간 내 에 채취 할 수 있 는 약초 의 최대 총 가 치 를 표시 합 니 다.
입 출력 사례 입력 703 71 100 69 12 출력 140 설명 / 제시 데이터 규모 와 약정 30% 의 데이터, 보증 m ≤ 10 3.100% 의 데이터 에 대하 여 1 ≤ m ≤ 10 4, 1 ≤ t ≤ 10 7, 및 m 보장×t<10 7，1≤ai，bi≤104 。
방법 1: 간단 하고 완전 가방 아이디어
각 가방 에서 얻 을 수 있 는 약초 의 상황 을 매 거 하여 각 공간 크기 의 최대 가 치 를 유지 합 니 다.
#include
#define ll long long
using namespace std;

struct node{
     
	int time, value;
}flower[10010];

ll dp[10000010];

int main(){
     
	int total, sum;
	scanf("%d%d", &total, &sum);
	for(int i=0; i<sum; i++){
     
		scanf("%d %d", &flower[i].time, &flower[i].value);
	}
	
	for(int i=1; i<=total; i++){
     
		for(int j=0; j<sum; j++){
     
			for(int k=0; k*flower[j].time<=i; k++){
     
				dp[i] = max(dp[i], dp[i-k*flower[j].time]+k*flower[j].value);
			}
		}
	}
	printf("%d", dp[total]);
	
	return 0;
}

사고방식 은 틀 리 지 않 았 지만 데이터 가 너무 커서 시간 을 초과 하 는 상황 이 발생 했다.
방법 2: 사고방식 최적화
방법 1: 가방 크기 (시간) 를 매 거 하고 약초 유형 에 따라 다양한 양의 약 초 를 넣 어 가방 에 넣 을 수 있 는 최대 가 치 를 유지 합 니 다.방법 2: 약초 타 입 에 따라 가방 을 넣 고 가방 마다 넣 을 수 있 는 최대 가 치 를 유지 합 니 다.방법 2 가 비교적 교묘 하 다.첫 번 째 약 초 를 채취 하 는 시간 이 가방 크기 j 보다 크 거나 같 으 면 이 약 초 를 넣 어 보 세 요.이렇게 하면 모든 상황 을 들 어 올 릴 수 있 을 뿐만 아니 라 약초 가 가방 에 들 어 가 는 수량 을 판단 하 는 것 도 피 할 수 있다.
#include
#define ll long long
using namespace std;

struct node{
     
	int time, value;
}flower[10010];

ll dp[10000010];

int main(){
     
	int total, sum;
	memset(dp, 0, sizeof(dp));
	
	scanf("%d%d", &total, &sum);
	for(int i=0; i<sum; i++){
     
		scanf("%d %d", &flower[i].time, &flower[i].value);
	}
	
	for(int i=0; i<sum; i++){
     	
	//      
		for(int j=flower[i].time; j<=total; j++){
     
		//           
			dp[j] = max(dp[j], dp[j-flower[i].time]+flower[i].value);
		}
	}
	
	printf("%lld", dp[total]);
	
	return 0;
}
javascript 빌트인 object 이해하기(1) - Number
JSP _actionTag(JavaBean)_page1

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage