가방 문제 상태 전이 방정식

1111 단어 #가방 문제동적 계획
만약 에 i 번 째 물품 의 전략 (놓 거나 놓 지 않 음) 만 고려한다 면 앞의 i - 1 번 물품 과 관련 된 문제 로 전환 할 수 있다.
  •      제 i 아 이 템 을 넣 지 않 으 면 '전 i - 1 아 이 템 을 v 용량 의 가방 에 넣 습 니 다' 로 바 뀌 고 가 치 는 f [i - 1] [v] 입 니 다.
  •      i 번 째 아 이 템 을 넣 으 면 '앞 i - 1 개 아 이 템 을 남 은 용량 v - w [i] 의 가방 에 넣 습 니 다' 로 전환 되 며, 최대 가 치 는 f [i - 1] [v - w [i]] + c [i] 입 니 다.
    • f[i][v]=max(f[i-1][v],f[i-1][v-w[i]+c[i]]);//  

for(v=V;v>0;v--)//  
f[v]=max(f[v],f[v-w[i]+c[i]]);

     
  • 가방 을 꽉 채 우 라 고 요구 하면 초기 화 할 때 f [0] 을 제외 하고 다른 f [1. V] 는 모두 - 표시
    • 로 설정 합 니 다.
  • 요구 가 없 으 면 등 을 가득 채 워 야 하 며 초기 화 시 f [0. V] 를 모두 0
    • 으로 설정 합 니 다.
     
    완전 가방 문제
      
    f[i][v]=max(f[i][v-w[i]+c[i]],f[i-1][v]);


for(v=1;v<=V;v++)
f[v]=max(f[v],f[v-w[i]]+c[i]);//f[v]   v

    f [i] [v] 를 고려 할 때, 이동 한 후에 쓰기 때문에 1 차원 배열 이 표시 하 는 f [v] 는 아직 쓰 이지 않 았 습 니 다. f [i - 1] [v] 를 표시 하고 f [v - w [i] 는 이미 쓰 여 있 습 니 다. f [i] [v - w] 를 표시 합 니 다.
    1 차원 f [v] = max {f [v], f [v - w [i]] + c [i]} 은 마침 2 차원: f [i] [v] = max {f [i - 1] [v], f [i] [v - w [i]] + c [i]} 을 나타 낸다.
    androidpn의 학습 연구 (3) androidpn-server 서버 몇 가지 설명
    018-mysql 사용자 정의 정규 교체 함수

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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