2019 아 리 교 모집 온라인 필기시험 - 프로 그래 밍 문제 두 번 째 문제 (패키지 포함)

원래 의 문 제 를 저장 하 는 것 을 잊 어 버 렸 지만, 문제 의 데 이 터 는 오히려 기억 하고 있다.
제목 설명:
당신 은 카 트 무료 기 회 를 가지 고 있 습 니 다. 무료 상품 은 소 포 를 통 해 배 송 되 지만 택 배 는 소포 의 최대 부피 V 와 최대 중량 W 를 제한 합 니 다.
몇 가지 상품 이 있 는데 상품 마다 4 개의 매개 변수 부피 Vi, 중량 Wi, 가치 Pi, 상품 수량 Ci, 상품 종류 Ti 가 있 습 니 다.
(상품 종 류 는 총 4 가지: 1, 2, 3, 4 이지 만 1 과 3 을 동시에 포장 할 수 없 음 을 알 고 있 습 니 다)
제한 을 초과 하지 않 는 최대 면제 가 치 를 계산 해 내다.
생각:
패 킷
앞의 두 개의 구속 (부피, 무게) 01 가방 에 대해 서 만 가능 합 니 다.1 과 3 의 상품 유형 이 충돌 하여 가방 을 나 누 었 는데, 사실은 2 조 에 불과 하 다.
원 제 를 저장 하지 않 았 기 때문에, 여기에 바로 방법 코드 를 붙 였 다.
private static int totalPrice(int categoryCount, int totalVolume, int totalWeight, int[] volume, int[] weight,
			int[] stock, int[] price, int[] itemType) {
		// categoryCount ---     
		// totalVolume ---     
		// totalWeight ---     
		// volume ---       
		// weight ---       
		// stock ---       
		// price ---       
		// itemType ---       
		
		/*
		 * dp[i][j][0]      i,   j ,     1       
		 * dp[i][j][1]      i,   j ,     3       
		 * 
		 * */
		int dp[][][] = new int[totalVolume + 1][totalWeight + 1][2];
		for (int i = 1; i <= categoryCount; i++) {
			if (itemType[i] == 1) {
				continue;
			}
			int stock_len = stock[i];
			while (stock_len > 0) {
				stock_len--;
				for (int j = totalVolume; j >= volume[i]; j--) {
					for (int k = totalWeight; k >= weight[i]; k--) {
						if (dp[j - volume[i]][k - weight[i]][0] + price[i] > dp[j][k][0]) {
							dp[j][k][0] = dp[j - volume[i]][k - weight[i]][0] + price[i];
						}
					}
				}
			}
		}
		for (int i = 1; i <= categoryCount; i++) {
			if (itemType[i] == 3) {
				continue;
			}
			int stock_len = stock[i];
			while (stock_len > 0) {
				stock_len--;
				for (int j = totalVolume; j >= volume[i]; j--) {
					for (int k = totalWeight; k >= weight[i]; k--) {
						if (dp[j - volume[i]][k - weight[i]][1] + price[i] > dp[j][k][1]) {
							dp[j][k][1] = dp[j - volume[i]][k - weight[i]][1] + price[i];
						}
					}
				}
			}
		}
		int result = Math.max(dp[totalVolume][totalWeight][0], dp[totalVolume][totalWeight][1]);
		return result;
	}

원 제 를 찾 으 면 추 후 업 데 이 트 될 것 입 니 다. 큰 남자 가 첫 번 째 문제 의 코드 를 저장 하고 있 기 를 바 랍 니 다. 토끼 를 세 는 것 을 가르쳐 주세요. 머리 가 아 픕 니 다.
필자 의 수준 은 한계 가 있 으 니, 잘못 이 있 으 면 시정 을 환영 합 니 다.

좋은 웹페이지 즐겨찾기