01 가방 문제(DP 동적 계획)

원제

가방 질문

n개의 무게와 가치가 각각 와이,vi인 물품이 있습니다.이 물품들 중에서 총 중량이 W를 초과하지 않는 물품을 골라 모든 선택 방안 중 가치 총화의 최대치를 구한다.
1<=n<=100
1<=wi,vi<=100
1<=W<=10000

샘플 입력

n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
W=5

샘플 출력

7(0, 1, 3번 아이템 선택)

코드

반복 쓰기 (기억 검색)

int n,W;
int w[MAX_N],v[MAX_N]
//     
int dp[MAX_N+1][MAX_N+1];
//  i           j   
int rec(int i,int j)
{
    if(dp[i][j]>=0)
    {
        return dp[i][j];
    }
    int res;
    if(i==n)
    {
        //      
        res=0;
    }
    else if(j

밀어쓰기(역방향)
dp[i][j]는 i번째 아이템부터 총 무게가 j보다 작은 부분을 고르는 것으로 정의됨
dp[n][j]=0
dp[i][j]= dp[i+1][j] (j
dp[i][j]= max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]) (j>=w[i])
4

int n,W;
int w[MAX_N],v[MAX_N]
//DP  
int dp[MAX_N+1][MAX_N+1];
void solve()
{
    for(int j=0;j<=W;j++)
    {
        dp[n][j]=0;
    }
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<=W;j++)
        {
            if(j

점차적 추이법(정방향 진행)
dp[i+1][j]는 이전 i개 아이템 중 총 무게가 j를 초과하지 않는 아이템을 선택할 때 총 가치의 최대치로 정의
dp[0][j]=0
dp[i+1][j]=dp[i][j]
(j
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]) (j>=w[i])
4

int n,W;
int w[MAX_N],v[MAX_N]
//DP  
int dp[MAX_N+1][MAX_N+1];
void solve()
{
    for(int j=0;j<=W;j++)
    {
        dp[0][j]=0;
    }
    for(int i=0;i

상태 전환
'전 i개 아이템 중 총 무게가 j를 초과하지 않을 때의 상태 선택'에서'전 i+1개 아이템 중 총 무게가 j를 초과하지 않을 때'와'전 i+1개 아이템 중 총 무게가 j+w[i]를 초과하지 않을 때의 상태 선택'으로 이동합니다.
4

int n,W;
int w[MAX_N],v[MAX_N]
//DP  
int dp[MAX_N+1][MAX_N+1];
void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i

주: 글의 내용은 에서 기원한다(제2판)

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

전략 게임(문제 해결 트리 DP)

처음 트리 DP를 씁니다. 트리 DP에서 DP의 "단계"는 일반적으로 깊이에서 얕은(하위 트리가 작은 것부터 큰 것까지) 순서로 사용됩니다. 대부분의 경우 우리는 귀속 방식을 이용하여 트리 DP를 실현한다. 각 노드...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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