package 算法設計與分析;
 import java.util.Arrays;
 import java.util.Scanner;
 //m表示的是背包的容量，a表示有多少種類的物品，數(shù)組w用與存放每類物品的重量，數(shù)組val用于存放每類物品的價值
 public class my {
     public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
         System.out.print("請輸入背包的容量:");
         int m = scanner.nextInt();
         Scanner inScanner = new Scanner(System.in);
         System.out.print("請輸入物品的個數(shù):");
         int a = inScanner.nextInt();
         int[] w = new int[a + 1];
         System.out.print("請輸入物品的重量:" + " ");
         for (int i = 1; i <= a; i++) {
             w[i] = inScanner.nextInt();
         }
         int[] val = new int[a+ 1];
         System.out.print("請輸入物品的價值:" + " ");
         for (int i = 1; i <= a; i++) {
             val[i] = inScanner.nextInt();
         }
         int n = val.length;
         int[][] path = new int[n +1][m+1 ];
         //創(chuàng)建二維數(shù)組
         //v[i][j]：表示在前i個物品中能夠裝入容量為j的背包中的最大價值
         int[][] v = new int[n +1][m + 1];
         //初始化第一行和第一列
         for (int i = 0; i < v.length; i++) {//v.length:獲取二維數(shù)組的行數(shù)
             v[i][0] = 0;//將第一列設置為0
         }
         for (int i = 0; i < v[0].length; i++) {//v[0].length：獲取二維數(shù)組的列數(shù)
             v[0][i] = 0;//將第一行設置為0
         }
         for (int i = 1; i < v.length; i++) {//int i = 1 不處理第一行
             for (int j = 1; j < v[0].length; j++) {//int j = 1 不處理第一列
                 if (w[i - 1] > j) {
                     v[i][j] = v[i - 1][j];
                 } else {
                     if (v[i - 1][j] < (val[i - 1] + v[i - 1][j - w[i - 1]])) {
                         v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                         //把當前情況記錄到path
                         path[i][j] = 1;
                     } else {
                         v[i][j] = v[i - 1][j];
                     }
                 }
             }
         }
         //輸出二維數(shù)組：
         for (int[] ints : v) {
             System.out.println(Arrays.toString(ints));
         }
         //輸出最后我們是放入的那些商品
         int i = path.length - 1;//行的最大下標
         int j = path[0].length - 1;//列的最大下標
         while (i > 0 && j > 0) {//從path的最后開始找
             if (path[i][j] == 1) {
                 System.out.printf("第%d個商品放入背包\n", i-1);
                 j -= w[i - 1];
             }
             i--;
         }
     }
 }