동적 기획----0-1 가방 문제

하나의 가방은 일정한 무게를 견딜 수 있는cap이 있고 N개의 물품이 있다. 모든 물건은 자신의 가치가 있다. 수조 v에 기록되어 있고 자신의 무게도 있다. 수조 w에 기록되어 있다. 모든 물품은 가방을 넣을 것인가 안 넣을 것인가만 선택할 수 있다. 가방의 무게를 초과하지 않는 전제에서 물품의 총 가치를 가장 많이 선택해야 한다.
주어진 물품의 무게 w가치 v 및 물품수 n과 무게받이cap.최대 총 가치를 되돌려 주십시오.
아이디어:
(n+1)(w+1) 2차원 그룹 dp를 구축하는데 그 중에서 dp[i][j]는 i개 물품을 넣을 때 총량이 j를 초과하지 않을 때의 최대 총 가치를 나타낸다.
dp[i][j]에서 i번째 아이템을 넣으려면 앞의 i-1개 아이템의 무게가 j-w[i]를 초과하면 안 되고, i번째 아이템을 넣지 않으려면 앞의 i-1개 아이템의 무게가 j를 초과하면 안 되고,
그래서 그 가치 dp[i][j]=max{dp[i-1][j-w[i]]+v[i], dp[i-1][j]}.
첫 번째 줄의 dp[0][j]에 대해 무게가 0을 초과하지 않기 때문에 물건을 넣지 않으면 가치가 0이고 첫 줄의 모든 값은 dp[0][j]=0이다.
제1열 dp[i][0]에 물품을 넣지 않으면 가치가 0이고 제1열의 모든 값은 dp[i][0]=0이다.

int maxValue(vector w, vector v, int n, int cap) {
	  //  dp    
	  int **dp = new int *[n+1];
	  for (int i = 0; i < n+1; i++)
	  {
		  dp[i] = new int [cap+1];
	  }
	  //     
	  for (int i = 0; i < cap+ 1; i++)
	  {
		  dp[0][i] = 0;//       ，      
	  }
	  for (int j = 0; j< n+1; j++)
	  {
		  dp[j][0] = 0;//       ，      
	  }
	  //     
	  for (int i= 1; i<= n; i++)//  
	  {
		  for (int j = 1; j <=cap; j++)//  
		  {
			  dp[i][j] = dp[i - 1][j];   //    i       
			  if (j - w[i-1] >= 0)//  w,v   0     ，       1
				  dp[i][j] = dp[i][j]>(dp[i - 1][j - w[i-1]] + v[i-1])? dp[i][j]: (dp[i - 1][j - w[i-1]] + v[i-1]);		  
		  }
	  }
	  return dp[n][cap];
  }