욕심 산법 - 최 적 화 된 적재

질문
문제 설명: 한 배의 적재량 은 C 입 니 다. 현재 n 개의 물건 을 드 리 겠 습 니 다. 그 중에서 모든 물건 의 무 게 는 Wi 입 니 다. 가능 한 한 많은 물건 을 배 에 실 어 달라 고 요구 합 니 다.
총 n + 1 줄 의 첫 번 째 줄 n 개 물체, 총 중량 C 뒤에 n 줄 을 입력 하고 줄 마다 물체 의 무게 wi)
가장 많은 아 이 템 을 출력 한 수량
샘플 입력

5 100
78
22
13
56
64

[샘플 출력]

3

전략 분석: 문제 가 가능 한 한 많은 물품 을 담 으 라 고 요구 하기 때문에 우 리 는 매번 물품 을 선택 할 때 가능 한 한 가 벼 운 물품 을 선택해 야 한다 고 생각 하기 쉽다. 그래 야 가능 한 한 많은 것 을 선택 할 수 있다. 따라서 1. 무게 에 따라 작은 것 부터 큰 것 까지 2. 순환 하여 옮 겨 다 닐 수 있다. 현재 무게 가 3 을 담 을 수 있 는 지, 담 을 수 있 는 것 이 있 는 것 이 있 는 지, 그렇지 않 으 면 순환 에서 물 러 날 수 있다.
코드

#include <cstdio>
#include <algorithm>
#define MAXN 1000 + 10
int w[MAXN];
int main() {
	int n, C, now = 0, cnt = 0;
	scanf("%d%d", &n, &C);
	for(int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
		
	std::sort(w+1, w+1+n);
	for(int i = 1; i <= n; i++) {
		if(now + w[i] <= C) { //       i     
			cnt++;
			now += w[i];
		}else 
			break;
	}
	printf("%d
", cnt); 
	return 0;
} 

질문
문제 설명: 현재 최대 적재량 이 M 인 트럭 과 N 가지 식품 이 있 는데 모든 식품 은 벌 크 로 나 눌 수 있다.이미 알 고 있 는 i 종의 식품 은 최대 Wi 킬로그램 을 가지 고 있 으 며, 그 상품 의 가 치 는 Vi 위안 / 킬로그램 입 니 다. 트럭 에 실 린 모든 물품 의 총 가치 가 가장 클 수 있 도록 선적 방안 을 확정 하 십시오.
n + 1 줄 의 첫 번 째 줄 을 입력 하 십시오: 두 개의 수 를 입력 하 십시오. 각각 화물차 의 최대 적재량 m (킬로그램) 과 화물 의 종류 n 다음 n 줄: 줄 당 두 개의 수, 첫 번 째 는 화물 의 보 유량 wi 킬로그램, 화물 의 단가 vi 원 / 킬로그램 1 ≤ m, n, wi, vi ≤ 100
출력 개수, 최대 가치
샘플 입력

5 100
78
22
13
56
64

샘플 출력

3

전략 분석: 제목 은 모든 화물 을 분리 할 수 있 고 불 러 오 는 총 가치 가 가장 크다 는 것 을 설명 한다. 그러면 우 리 는 모든 물품 의 단위 가 치 를 계산 한 다음 에 단위 가치 에 따라 큰 것 에서 작은 것 으로 순 서 를 매 겨 야 한다. 따라서 1. 데 이 터 를 읽 을 때 단위 가치 2 를 계산 하고 단위 가치 에 따라 큰 것 에서 작은 것 으로 순 서 를 매 길 수 있다.반복 해서 옮 겨 다 니 며 현재 의 가장 큰 가 치 를 담 을 수 있 는 것 은 모두 담 습 니 다. 그렇지 않 으 면 남 은 공간 을 가득 채 웁 니 다.
코드

#include<cstdio>
#include<algorithm>
#define MAXN 100 + 15
struct food{
	int w;
	int v;
}s[MAXN]; 

bool cmp(food a, food b) { //          
	return a.v > b.v;
}

int main() {
	int m, n, sum = 0, weight = 0, j = 1;
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &s[i].w, &s[i].v);
	}
	std::sort(s+1, s+1+n, cmp);
	while(weight + s[j].w <= m) {	//                
		weight += s[j].w;
		sum += s[j].w * s[j].v;
		j++;
	}
	sum += (m - weight) * s[j].v;	//       
	printf("%d
", sum);
	return 0;
}

소결: 어떻게 하면 매번 의 선택 이익 화 를 최대 로 할 수 있 는 지 알 아야 한다 (거의 모든 욕심 이 먼저 순 위 를 매 겨 야 한다)