가방 9 강 에 대한 총괄 분석 (지속 업데이트, 미 완성)
51313 단어 기본 알고리즘 템 플 릿 문제동적 계획알고리즘
질문
제목 설명
N 개의 아 이 템 과 1 개의 용량 이 m 인 가방 이 있 습 니 다.각 아 이 템 은 1 회 만 사용 할 수 있 습 니 다.제 i 물품 의 부 피 는 vi 이 고 가 치 는 wi 이다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 총 부피 가 가방 용량 을 초과 하지 않 고 총 가치 가 가장 큽 니까?수출 최대 가치.데이터 범위 0 0i, wi ≤ 1000
문제 분석
상태 표시: f (i, j) 로 이전 i 개 물 품종 의 선택 부피 가 j 와 같은 모든 선택 법의 최대 가 치 를 나타 낸다.
f (i - 1, j), f (i - 1, j - 1), f (i - 1, j - v), f (i - 1, 0) 가 확정 되면 상태 f (i, j) 는 f (i - 1, j) 또는 f (i - 1, j - v) 에서 옮 길 수 있다.
상태 이동: f (i, j) = {f (i − 1, j), 아 이 템 f (i − 1, j − v) + w 를 선택 하지 않 고, 아 이 템 f (i, j) = \ 왼쪽 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {정렬} f (i - 1, j), 아 이 템 을 선택 하지 않 고 \ \ \ \ \ f (i - 1, j - v) + w, 아 이 템 선택 \ \ \ \ 엔 드 {정렬} \ \ \ \ 오른쪽. f (i, j) = {f (i - 1, j), 아 이 템 을 선택 하지 않 고, 아 이 템 f (i - 1, j - v) + w, 아 이 템 을 선택 하지 않 고, 아 이 아 이 템 \ \ \ \ \ \ \ \ \ \ \ \ j − v)+ w, 제 i 건 아 이 템 상태 이전 방정식 을 선택 하 십시오.
f(i, j ) = max{f(i-1, j), f(i-1, j-v)+w}c + + 코드 구현#include 스크롤 배열 최적화
그러나 모든 f (i) 의 상 태 는 f (i - 1) 의 상태 에서 만 전 환 된 것 으로 밝 혀 졌 습 니 다. f 배열 의 1 차원 을 취소 하고 2 차원 만 저장 할 수 있 습 니 다. 현재 i 층 은 덮어 쓰 지 않 은 i - 1 층 의 덮어 쓰 지 않 은 데이터 로 상태 이전 방정식 을 진행 할 수 있 습 니 다.
f(j) = max(f(j), f(j-vi)+wi)그러나 주의해 야 할 것 은 우리 의 i 층 과 j 층 은 모두 하나의 배열 f 가 있 고 우리 에 게 필요 한 것 은 덮어 쓰 지 않 은 i - 1 층 의 데이터 업데이트 i 층 입 니 다. 모든 역순 으로 부피 j 를 들 어야 합 니 다.c + + 코드 구현
#include 2. 완전 가방 문제
문제 설명
N 개 아 이 템 과 1 개 용량 이 m 인 가방 이 있 습 니 다. 각 아 이 템 은 무한 회 사용 가능 합 니 다. i 개 아 이 템 의 부 피 는 vi, 가 치 는 wi 입 니 다. 어떤 아 이 템 을 가방 에 넣 으 면 이 아 이 템 의 총 부피 가 가방 용량 을 초과 하지 않 고 총 가치 가 가장 큽 니 다. 수출 최대 가치. 데이터 범위 0 i, wi ≤ 1000
소박 한 방법 분석
완전 가방 문제 와 0 - 1 가방 문제 의 유일한 차 이 는 모든 아 이 템 이 무한 회 상태 로 우리 가 똑 같이 f (i, j) 를 설정 할 수 있다 는 것 이다.⌋ \ lfloor log 2 (j) \ rfloor ⌊ log 2 (j) ⌋) 그래서 우 리 는 0 - 1 가방 과 유사 한 상태 i - 1 에서 상태 i 로 이동 하 는 상태 이동 방정식 을 얻 을 수 있다. 단지 0 - r 의 한 순환, 즉
for(int k = 0; j -k * v >=0 ; k++) f[i][j] = max(f(i, j), f(i-1, j-k*v)+k*w)c + + 코드 구현#include 최적화 하 다.
소박 한 방법 에서 의 상태 전이 방정식 은 하나의 순환 으로 표시 할 수 있다. 사실은 우 리 는 순환 을 전개 할 수 있다. 이렇게
f(i, j) = max{ f(i-1, j), f(i-1, j-v)+w, f(i-1, j-2*v)+2*w, ... , f(i-1, j-r*v)+r*w} 동시에 우 리 는 다른 f (i, j - v) 를 전개 할 수 있다. 2 차원 이 0 보다 크 기 때문에 그 가 최종 적 으로 전개 한 마지막 항목 도 반드시 f (i - 1, j - r * v) 상태 f(i, j-v) = max{ f(i-1, j-v), f(i-1, j-2*v)+w, ..., f(i-1, j-r*v)+(r-1)*w} 이다.위의 두 식 을 통 해 우 리 는 더욱 간편 한 상태 전이 방정식 을 발견 할 수 있다.f(i, j) = max{f(i-1, j), f(i, j-v)+w} 이때 우 리 는 계산 한
f(i, j-v) 으로 상태 이동 을 해 야 한다. 모든 f(i-1, ...) 의 상 태 를 계산 할 필요 가 없다. 이번 에는 0 - 1 가방 의 스크롤 배열 처럼 직접 1 차원 배열 로 공간 을 최적화 하 는 것 을 직접 고려 해 야 한다. 그래서 f(j) = max(f(j), f(j-v)+w) 여기 서 우리 가 필요 로 하 는 f (j - v)i 층 의 j - v 입 니 다. 업 데 이 트 된 것 입 니 다. 모든 부 피 를 정렬 해 야 합 니 다. 교체 가 끝 난 후 f (m) 가 답 입 니 다. 그 는 부피 가 m 인 가방 에 모든 n 가지 물건 을 넣 는 최대 가치 수 를 대표 합 니 다.c + + 코드 구현
#include 3. 다 중 가방 문제
문제 설명
N 가지 아 이 템 과 1 개 용량 이 m 인 가방 이 있 습 니 다. i 가지 아 이 템 은 si 개, 부 피 는 vi, 가 치 는 wi 입 니 다. 어떤 아 이 템 을 가방 에 넣 으 면 이 아 이 템 들 의 총 부피 가 가방 용량 을 초과 하지 않 고 총 가치 가 가장 큽 니 다. 수출 최대 가치.
1. 소박 한 방법
적 용 된 데이터 범위
0 0i, vi,wi≤100
사고 와 분석
우선 이 문 제 는 완전 가방 문제 와 유사 하 다. 다만 각 아 이 템 의 수량 은 무한 이 아니 라 유한 하 다. 소박 하고 완전 가방 을 사용 하 는 방법 을 고려 하여 폭력 은 s 차 순환 상태 로 이전 한다.
for(int k = 0; k <= s && j -k * v >=0 ; k++) f[i][j] = max(f(i, j), f(i-1, j-k*v)+k*w) 시간 복잡 도: O (nms) 작은 데 이 터 는 ac 가 가능 하 다.c + + 코드 구현
#include 2. 이 진 최적화
적 용 된 데이터 범위
0 0 0i, vi,wi≤2000
사고 와 분석
만약 에 예전 의 소박 한 방법 을 사용 했다 면 O (nms) 시간 복잡 도 는 최대 4 * 109 회 계산 하고 1s 내 에 완성 할 수 없 으 며 속도 가 빠 른 방법 을 고려 해 야 한다.
어떤 s 에 대해 우리 가 선택해 야 할 것 은 s 이내 의 임의의 수량의 아 이 템 입 니 다. 그러면 더 적은 숫자 로 1 – s 내의 모든 수 를 표시 할 수 있 습 니까? 그래서 우 리 는 s 개 수 를 1, 2, 4, 8,..., r, s - r (다른 r = 2 * 8970 ° l o g 2 s * 8971 ° ^ {\ lfloor log 2s \ rfloor} * 8970 ° log 2 s * 8971 °) 로 나 눌 수 있 습 니 다.이 수 는 한 번 에 1 - s 이내 의 모든 수 를 표시 할 수 있 기 때문에 문 제 는 마지막 에 새로운 0 - 1 가방 문제 로 바 뀌 었 다.
c + + 코드 구현
#include 3. 단조 로 운 대기 열 최적화
적 용 된 데이터 범위
0 0 0 i, vi, wi ≤ 20000 주: 본 문제 가 가장 어렵 습 니 다. 마지막 으로 미끄럼 창 문제 로 전환 하고 단조 로 운 대기 열 로 최적화 합 니 다. 미끄럼 창 문 제 를 업데이트 한 다음 에 가방 문 제 를 작성 합 니 다. 3 사실은 남자 8 문제 중의 Coins 문제 와 같 습 니 다.
질문
문제 설명
N 가지 아 이 템 과 용량 이 m 인 가방 이 있 습 니 다.
아 이 템 은 모두 세 종류 가 있 습 니 다:
첫 번 째 아 이 템 은 1 회 (0 - 1 가방) 만 사용 할 수 있 고, 두 번 째 아 이 템 은 무한 회 (완전 가방) 만 사용 할 수 있 으 며, 세 번 째 아 이 템 은 최대 si 회 (다 중 가방) 만 사용 할 수 있 으 며, 각 부 피 는 vi 이 고 가 치 는 wi 입 니 다. 어떤 아 이 템 을 가방 에 넣 으 면 아 이 템 의 부 피 를 합 쳐 가방 용량 을 초과 하지 않 고 가 치 를 합 쳐 최대 로 출력 할 수 있 는 지 알 아 보 세 요.
문제 분석
상 태 는 실제 본 문 제 는 앞의 세 가지 기본 적 인 가방 문제 의 융합 일 뿐 상 태 는 예전 에 i 개 물품 에서 선택 한 것 이 고 전체 부피 가 j 를 초과 하지 않 는 모든 선택 상태 계산 상태 계산 상 태 는 상기 세 가지 가방 문제 의 상태 전이 방정식 을 계속 사용 하고 데 이 터 를 얻 을 때 어떤 문제 가 대응 하 는 방정식 을 선택 하 는 지 판단 하면 된다.
(여기 서 다 중 가방 문제 에 대해 바 이 너 리 최적화 로 0 - 1 가방 문제 로 전환 하여 상태 이전 은 두 가지 밖 에 없습니다)
여기 서 두 가지 기본 적 인 상태 전이 방정식 을 복습 합 니 다. 0 - 1 가방: 윗 층 의 상태 가 필요 합 니 다. 모든 이곳 의 부 피 는 역순 으로 매 거 집 니 다.
f(j) = max(f(j), f(j-v)+w) 완전 가방: 이 층 이 업 데 이 트 된 상태 가 필요 합 니 다. 순서 매 거 부피: f(j) = max(f(j), f(j-v)+w) (구체 적 인 추 도 는 위 에 있 습 니 다)C + + 코드 구현
#include
", f[m]);
return 0;
}
5. 2 차원 비용 의 가방 문제
문제 설명
N 개의 아 이 템 과 1 개의 용량 이 V 인 가방 이 있 는데 가방 이 감당 할 수 있 는 최대 무 게 는 M 이다.
물건 마다 한 번 만 사용 할 수 있 습 니 다. 부 피 는 vi 이 고 무 게 는 mi 이 며 가 치 는 wi 입 니 다.
어떤 아 이 템 을 가방 에 넣 으 면 아 이 템 의 총 부피 가 가방 용량 을 초과 하지 않 고 총 무 게 는 가방 이 감당 할 수 있 는 최대 무 게 를 초과 하지 않 으 며 가치 총화 가 가장 크다. 수출 최대 가치.
문제 분석
2 차원 비용 의 가방 문 제 는 일반적인 0 - 1 가방 문제 보다 한 가지 제한 조건 이 더 많 을 뿐이다. 품질 은 상태 표시 와 이전 시 이 조건 을 더 하면 된다. 상태 표시 f (i, j, k) 는 모든 이전 i 개 물품 중에서 선택 하고 전체 부 피 는 j 를 초과 하지 않 으 며 총 질량 은 k 를 초과 하지 않 는 모든 선택 상태 이전 f (i, j, k) = {f (i - 1, j, k)i 번 째 아 이 템 f (i − 1, j − v i, k − m i) + w i 를 선택 하지 않 고, i 번 째 아 이 템 f (i, j, k) = \ \ 왼쪽 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f (i - 1, j - v i, k - m i, k - m i) + w i, 첫 번 째 아 이 템 \ \ \ \ \ \ \ 엔 드 {정렬} \ \ \ 오른쪽. f (i, j, k) = {f (i - 1, j - v i, k) 아 이 템 을 선택 하지 않 고, 두 번 째 아 이 템 을 선택 하지 않 고 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 오른쪽. f (i, j, k 1, j − vi, k − mi) + wi, i 번 째 를 선택 하면
f(i, j, k) = max(f(i-1, j, k), f(i-1, j-v, k-m)+w)C + + 코드 구현#include 질문
7. 의존 하 는 가방 문제
8. 가방 문제 구 안 수
9. 가방 문 제 는 구체 적 인 방안 을 요구한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JZOJ.3432 [GDOI 2014 시뮬레이션] 서버 문제 해결 보고서이 서버의 번호는 1, 2,..., n이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.서버 i에 파일을 복사하려면 ci가 필요합니다.직접 복제를 통해 파일을 얻지 못한 서버에 대해 i+...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
