JAvaダイナミックプランニング(リュックサック問題)コード実装

/**
 * @author Drug
 * @create 2020-05-12 15:46
 */
public class KnapsackProblem {
     
    public static void main(String[] args) {
     
        //    
        int[] w = {
     1, 4, 3};
        //    
        int[] value = {
     1500, 3000, 2000};
        //    
        int m = 4;
        //    
        int n = value.length;
        //             
        int[][] v = new int[n + 1][m + 1];
        //           
        int[][] path = new int[n + 1][m + 1];

        //         0
        for (int i = 0; i < v.length; i++) {
     
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
     
            v[0][i] = 0;
        }

        //              
        for (int i = 1; i < v.length; i++) {
     
            //     1 4
            for (int j = 1; j < v[0].length; j++) {
     
                //                 
                if (w[i - 1] > j) {
     
                    //          
                    v[i][j] = v[i - 1][j];
                } else {
     
                    //                   
                    //                                        
                    //value[i - 1] + v[i-1][j-w[i-1]]                       
                    //v[i-1][j]             
                    //              
                    if ((value[i - 1] + v[i - 1][j - w[i - 1]]) >= v[i - 1][j]) {
     
                        //     
                        v[i][j] = (value[i - 1] + v[i - 1][j - w[i - 1]]);
                        //   [i][j]        
                        path[i][j] = 1;
                    } else {
     
                        //                
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        
        //        
        for (int i = 0; i < v.length; i++) {
     
            for (int j = 0; j < v[0].length; j++) {
     
                System.out.print(v[i][j] + "    ");
            }
            System.out.println();
        }

        System.out.println("           ");
        //    , path      1   
        //path   
        int i = path.length - 1;
        //path   
        int j = path[0].length - 1;
        //           
        while(i > 0 && j>0){
     
            //             
            if(path[i][j] == 1){
     
                System.out.println("   "+i+"   ");
                //    
                j -= w[i-1]; 
            }
            //   1
            i--;
        }
    }
}