アルゴリズム-01リュックサック問題【f[i][j]に対するjは超えない、ちょうど等しい、残りの空間の詳細】

  N           V    。          。

  i         vi，    wi。

           ，                 ，      。
      。

    
       ，N，V，     ，             。

     N  ，       vi,wi，     ，      i          。

    
      ，      。

    
0<N,V≤1000
0<vi,wi≤1000
    
4 5
1 2
2 4
3 4
4 5
    ：
8

for(int i = 1; i <= n; i++ ){// i  
	for(int j = 0; j <= v; j++ ){
		f[i][j] = f[i - 1][j];//   i   
		if(j >= vx[i])//            j-vx[i] ，     v[i]   ，     j 
			f[i][j] = max(f[i][j], f[i - 1][j - vx[i]] + m[i]);//   j-vx[i]，        i   ，
			//   f[i][j] ：   i ，     j     （        f[i-1][j - vx[i]       + m[i]  ）
	}
}

if(j >= vx[i])
	f[i][j] = max(f[i][j], f[i - 1][j - vx[i]] + m[i]);

f [3][5] = max(f[2][5], f[2][5-vx[3]] + m[3])

for(int i = 1; i <= n; i++ ){// i ，    2    
		for(int j = 0; j <= v; j++ ){//      
			f[i][j] = f[i - 1][j];//   i   
			if(j >= vx[i] && (j == vx[i] || f[i - 1][j-vx[i]] != 0))
				f[i][j] = max(f[i][j], f[i - 1][j - vx[i]] + m[i]);//   j-vx[i]，        i   ，
				//      i    ，       i（   j>=vx[i]）
		}
	}

if(j >= vx[i] && (j == vx[i] || f[i - 1][j-vx[i]] != 0))

         f[ n ][0 ~ v]      ，                 。

for(int i = 1; i <= n; i++ ){// i  
		for(int j = 0; j <= v; j++ ){//       j 
			f[i][j] = f[i - 1][j];//   i   
			if(j + vx[i] <= v)//     
				f[i][j] = max(f[i][j], f[i - 1][j + vx[i]] + m[i]);//   j+vx[i]，        i   ，
				//             ，  i    2，        7 ，           9      
		}
	}

if(j + vx[i] <= v)//     
	f[i][j] = max(f[i][j], f[i - 1][j + vx[i]] + m[i]);

         f[ n ][0 ~ v]      ，                 。