1.01 가방

N개 아이템과 W 용량의 백팩이 있습니다.i(i=0,1,,,N-1)개 아이템을 넣으면 소모되는 용량은 W[i]이고 얻는 가치는 V[i]이다.어떤 아이템을 가방에 넣으면 가치 총화를 최대화할 수 있는지 구해보세요.

dp[i][j]:     0~i,   j       
vector>dp(N,vector(W+1,0));
for(int i=1;i=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//  i  / 
        else
            dp[i][j]=dp[i-1][j];
return dp[N-1][W];
//    ，      dp
vectordp(W+1,0);
for(int i=0;i=0;--j)
        if(j>=w[i])//a
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        else 
            dp[j]=dp[j];//b
return dp[W];
//   a b
vectordp(W+1,0);
for(int i=0;i=w[i];--j)        
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[W];

전체 패키지: W 용량을 모두 채워야 하는 최대 가치와

초기화 시 dp[i][0]=0, 기타 dp[i][j]는 INTMIN, 컨디션이 0에서 옮겨온 게 확실하다는 걸 확인할 수 있어요.

dp[i][j]:     0~i,   j       
vector>dp(N,vector(W+1,INT_MIN));
for(int i=0;i=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//  i  / 
        else
            dp[i][j]=dp[i-1][j];
return dp[N-1][W];
//    ，      dp
vectordp(W+1,INT_MIN);
dp[0]=0;
for(int i=0;i=0;--j)
        if(j>=w[i])//a
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        else 
            dp[j]=dp[j];//b
return dp[W];
//   a b
vectordp(W+1,INT_MIN);
dp[0]=0;
for(int i=0;i=w[i];--j)        
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[W];

2. 완전 가방

N가지 아이템과 W 용량의 가방 1개가 있으며, 각 아이템은 무한 개 사용 가능.제i(i=0,1,2,,,N-1)종의 아이템을 넣는 데 소모되는 공간은 w[i]이고 얻는 가치는 v[i]이다.구해: 어떤 물품을 가방에 넣으면 이 물품들이 소모하는 공간이 가방 용량을 초과하지 않고 가치가 가장 크다.
전이 방정식이 다르고(0-1 가방 dp[i][j]는 모두 상층 dp[i-1][]에서 유도할 수 있으며 완전 가방 dp[i][j]는 dp[i-1][]와 dp[i][] 두 층에서 유도할 수 있다) 2차원 dp가 1차원 dp로 내려갈 때 역행하는 방향이 다르기 때문에 2차원 그림을 그리면 이해하기 쉽다.

dp[i][j]:     0~i,   j       
vector>dp(N,vector(W+1,0));
for(int i=1;i=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);//  i  / 
        else
            dp[i][j]=dp[i-1][j];
return dp[N-1][W];
//    ，      dp
vectordp(W+1,0);
for(int i=0;i=w[i])//a
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        else 
            dp[j]=dp[j];//b
return dp[W];
//   a b
vectordp(W+1,0);
for(int i=0;i