0 - 1 가방 문제 동적 계획

분석 은 다음 과 같다.
제목.
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 물품 의 무 게 는 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
기본 적 인 사고방식
이것 은 가장 기본 적 인 가방 문제 로 모든 아 이 템 이 하나 밖 에 없 으 므 로 놓 거나 놓 지 않 는 것 을 선택 할 수 있 는 것 이 특징 이다.
하위 문제 로 상 태 를 정의 합 니 다: 즉 f [i] [v] 는 앞의 i 개 아 이 템 을 v 용량 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가 치 를 표시 합 니 다.그 상태 전이 방정식 은 다음 과 같다.
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
이 방정식 은 매우 중요 하 다. 기본적으로 가방 과 관련 된 모든 문제 의 방정식 은 그것 에서 파생 된 것 이다.따라서 이 를 상세 하 게 설명 할 필요 가 있다. "앞의 i 개 물품 을 v 용량 의 가방 에 넣는다" 는 문 제 는 i 개 물품 의 전략 (놓 거나 놓 지 않 는 다) 만 고려 하면 앞의 i - 1 개 물품 과 관련 된 문제 로 바 뀔 수 있다.만약 에 i 번 째 아 이 템 을 넣 지 않 으 면 문 제 는 '전 i - 1 개 아 이 템 을 v 용량 의 가방 에 넣 습 니 다' 로 바 뀌 고 가 치 는 f [i - 1] [v] 입 니 다.i 번 째 아 이 템 을 넣 으 면 문 제 는 '앞의 i - 1 아 이 템 을 남 은 용량 v - c [i] 의 가방 에 넣 기' 로 바 뀌 는데 이때 얻 을 수 있 는 가장 큰 가 치 는 f [i - 1] [v - c [i]] 와 i 번 째 아 이 템 을 넣 어 얻 을 수 있 는 가치 w [i] 이다.
  단계 I (아 이 템 수량)
  각 단계 의 상태: 전 i 개 아 이 템 의 총 용량 은 v 의 최대 가 치 를 초과 하지 않 습 니 다. f[i][v]
  상태 전이 방정식  
v 가 c [i] 보다 크 면 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
c [i] 보다 작 을 때 f[i][v] = f[i-1][v]
 경계 제어  I =0  또는 v = 0 시 f [i] [v] = 0
for i:=1 to v do f[0,i]:=0;
for i:=1 to n do f[i,0]:=0;
for i:=1 to n do
for j:=1 to v do
begin
if j>=c[i] then f[i,j]:=max(f[i-1,j-c[i]]+w[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
자세 한 설명:
테스트 데이터:
3 10
4 3 
5 4
6 5
c [i] [j] 배열 은 1, 2, 3 번 아 이 템 을 순서대로 선택 한 최대 가 치 를 저장 합 니 다.
이 최대 가 치 는 어떻게 얻 은 것 입 니까?가방 용량 이 0 부터 1 번 아 이 템 을 먼저 시험 해 보 세 요. 0, 1, 2 의 용량 은 모두 넣 을 수 없습니다. 그래서 0, 가방 용량 이 3 이면 안에 넣 습 니 다. 이렇게 하면 이 가방 용량 이 4, 5, 6,... 10 일 때 가장 좋 은 방안 은 모두 넣 는 것 입 니 다. 만약 1 번 아 이 템 을 가방 에 넣 으 면 2 번 아 이 템 을 다시 봅 니 다. 가방 용량 이 3 일 때 가장 좋 은 방안 은 윗 줄 의 가장 좋 은 방안 c 가 4 이 고 가방 용량 이 5 일 때 입 니 다.가장 좋 은 방안 은 자신의 무게 5. 가방 용량 이 7 일 때 5 에 한 값 을 더 한 것 이 분명 하 다.누구 추가 요?7 - 4 = 3 일 때 가 분명 합 니 다. 이전 줄 c3 의 가장 좋 은 방안 은 4 입 니 다. 그래서.전체적인 가장 좋 은 방안 은 5 + 4 가 9 이다. 이렇게 일렬 로 미 루 는 것 이다.가장 오른쪽 아래 에 놓 인 데이터 가 가장 큰 가치 입 니 다.(세 번 째 줄 의 가방 용량 이 7 일 때 가장 좋 은 방안 은 그 자체 의 6 이 아니 라 이전 줄 의 9 입 니 다. 이때 3 번 아 이 템 이 선택 되 지 않 았 다 는 뜻 입 니 다. 1, 2 번 아 이 템 을 선 택 했 기 때문에 9.)
참조 코드 는 다음 과 같 습 니 다.
질문

#include <iostream>
using namespace std;

int max(int a,int b)
{
 int temp=b;
 if (a>b)temp=a;
 return temp;
}

int main()
{
 int N,V;
 int sum[101][100]={0};
 int i,j;
 int c[100]={0},w[100]={0};
 while (cin>>N>>V) {
  for(i=1;i<=N;i++)cin>>c[i]>>w[i];
  
  for(i=0;i<=N;i++)
   for(j=0;j<=V;j++)
    sum[i][j]=0;

   cout<<"    ："<<endl;

   for(i=1;i<=N;i++)
    for(j=1;j<=V;j++)
    {
     if (j>=w[i])sum[i][j]=max(sum[i-1][j],sum[i-1][j-w[i]]+c[i]);
     else sum[i][j]=sum[i-1][j];
     
     cout<<sum[i][j]<<" ";
     if(j%V==0)cout<<endl;
    }
    cout<<"    ："<<sum[N][V]<<endl;
 }
 return 0;
}