알고리즘 디자인 과 분석 - 동적 계획

4064 단어 알고리즘 설계 및 분석동적 계획
동적 계획
먼저 컴퓨터 문 제 를 규모 가 작은 하위 문제 로 분해 한 다음 에 아래 에서 위로 각 하위 문 제 를 풀 고 하위 문제 의 해 제 를 데이터 구조 에 저장 합 니 다.
  • 서브 구조 최적화
  • 중첩 자 문제
    • 문제 실례
    (1) 0 - 1 가방 문제
  • 1 개 용량 이 C 인 가방 과 n 개 아 이 템 중 i 번 째 아 이 템 의 부 피 는 weight [i] 이 고 그 가 치 는 value [i] 입 니 다. 1 개 아 이 템 을 가방 에 넣 거나 가방 에 넣 지 않 습 니 다. 가방 안의 아 이 템 은 총 무게 가 C 를 초과 하지 않 고 총 가격 이 최대 치
    • 에 달 합 니 다.
  • 하나의 배열 f [i] [j] 로 총 i 개의 물품 이 있 고 용량 이 j 인 상황 에서 가방 문제 가 가장 좋 은 것 으로 나 타 났 다.첫 번 째 아 이 템 은 가방 에 넣 거나 가방 에 넣 지 않 는 것 을 선택 할 수 있 습 니 다 (이것 이 바로 0 과 1).
  • 가방 에 넣 으 면 (전 제 는 내 려 놓 을 수 있다): 
    • f[i][j]=f[i－1][j-weight[i]+value[i];
  • 가방 에 넣 지 않 으 면: 
    • f[i][j]=f[i－1][j];
  • 상태 전이 방정식 
    • f[i][j]=max(f[i－1][j],f[i-1][j-weight[i]+value[i]);

    (2) 완전 가방 문제 (1)
  • 1 개 용량 이 C 인 가방 과 n 개 아 이 템, i 번 째 아 이 템 의 부 피 는 weight [i] 이 고 그 가 치 는 value [i] 입 니 다. 모든 아 이 템 은 무한 여러 개가 있 습 니 다. 지금 가방 에 물건 을 넣 으 면 가방 안의 아 이 템 의 가치 가 가장 큽 니 다
  • 하나의 배열 f [i] [j] 로 "모두 i 개의 물건 이 있 습 니 다. j 는 가방 에 수용 할 수 있 는 무게 이 고 i 가지 물건 이 있 을 때 i 번 째 물건 을 찾 거나 찾 지 않 거나 얼마나 찾 는 지 에 대해 서 는 관심 이 없습니다." 라 고 말 했다.
  • 상태 전이 방정식 
    • f[i][j]=max(f[i－1][j], f[i][j-weight[i]]+value[i], i=0,...,N);

    (3) 완전 가방 문제 (2)
  • 하나의 배열 f [i] [j] 로 총 i 개의 물품 이 있 고 j 는 가방 에 수용 할 수 있 는 무게 이 며 N 가지 물품 이 있 습 니 다. 모든 물품 에 대해 적어도 하 나 를 포함한다 고 가정 합 니 다. 도대체 몇 개 를 포함 하 는 지 에 대해 우 리 는 관심 이 없습니다.
  • 상태 전이 방정식 
    • f[j]=max{f[j-weight[i]]＋value[i], i=0,...,N｝

    (4) 최소 동전 거스름돈 문제 (1)
  • 서로 다른 액면가 의 동전 몇 가 지 를 주 었 습 니 다. 예 를 들 어 15, 10, 20, 50, 100, 그리고 각 동전 의 개 수 는 무한 많 습 니 다. 어떻게 몇 가지 동전 으로 특정한 액면가 의 돈 을 조합 하여 동전 의 개 수 를 가장 적 게 합 니까?
  • j 가 0 원 을 얼마나 찾 아야 하 는 지, i 종 동전 이 있다 고 가정 하면 0 시 에 i 종 동전 을 찾 을 때 우 리 는 찾 거나 찾 지 않 는 것 만 고려 하고 몇 개 를 찾 는 지 에 대해 우 리 는 관심 이 없다.
  • 상태 전이 방정식 
    • f[i][j]=min(f[i－1][j],f[i][j-coins[i]]+1);

    (5) 최소 동전 거스름돈 문제 (2)
  • j 가 0 을 얼마나 찾 아야 하 는 지, N 가지 동전 이 있다 고 가정 하면 모든 동전 에 대해 우 리 는 f (i) 에 적어도 하나의 coins [j] (j = 0, 1... N) 가 포함 되 어 있다 고 가정 한 다음 에 필요 한 최소 동전 은 f (j - coin [i] + 1 이 라 고 가정 할 수 있다. 마지막 으로 이 N 번 가설 에서 가장 작은 것 을 선택 하면 f (i) 이다.
  • 상태 전이 방정식 
    • f[j]= min{f[j-coins[i]]＋1, i=0,...,N};

    (6) Word Break 문제
    비어 있 지 않 은 문자열 s, 비어 있 지 않 은 문자열 사전 을 요구 합 니 다. s 가 빈 칸 을 통 해 하나의 서열 을 구성 할 수 있 는 지 판단 하 는 것 은 사전 의 여러 단어 입 니 다. 예 를 들 어 s = "leetcode", dict = ["leet", "code"] 입 니 다. "leetcode" 는 "leet code" 로 바 꿀 수 있 기 때문에 1 을 되 돌려 줍 니 다.
  • 상태 전이 방정식 
    • dp[i+Len]=dp[i]&&dict.find(s.substr(i,Len)); #Len:[minlen,maxlen],i:[0,s.size()]
    hdu 3939 (피타 고 라 스 + 배척)
    안드로이드 애니메이션 기초 - 애니메이션 사례 변환(4)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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