2019 아 리 교 모집 온라인 필기시험 - 프로 그래 밍 문제 두 번 째 문제 (패키지 포함)
2297 단어 알고리즘ACM필기시험 프로 그래 밍 문제
제목 설명:
당신 은 카 트 무료 기 회 를 가지 고 있 습 니 다. 무료 상품 은 소 포 를 통 해 배 송 되 지만 택 배 는 소포 의 최대 부피 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;
}
원 제 를 찾 으 면 추 후 업 데 이 트 될 것 입 니 다. 큰 남자 가 첫 번 째 문제 의 코드 를 저장 하고 있 기 를 바 랍 니 다. 토끼 를 세 는 것 을 가르쳐 주세요. 머리 가 아 픕 니 다.
필자 의 수준 은 한계 가 있 으 니, 잘못 이 있 으 면 시정 을 환영 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.