完美世界的两个编程题

```
/** * 背包问题  */ 
public static void DPweight() {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt(); 
    int costValue[] = new int[n];
    int weightVaule[] = new int[n];
    int i, j = 0; 
    for (i = 0; i<n; i++)
         costValue[i] = scanner.nextInt();
    for (i = 0; i<n ; i++)
          weightVaule[i] = scanner.nextInt(); 
    int t = scanner.nextInt(); 
    int[][] dp = new int[n + 1][t + 1];
     for (i = 0; i<n+1; i++) 
        for (j = 0; j<n+1; j++)
                 dp[i][j] = 0;
    for (i = 1; i<n+1; i++) {
       for (j = 1; j<n+1; j++)  {
          if (j >= weightVaule[i - 1])
                 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weightVaule[i - 1]] + costValue[i - 1]); 
          else  dp[i][j] = dp[i - 1][j]; 
     }
 }
        System.out.print(dp[n][t]); 
} 
/** * 硬币问题  *  */
 public static void DPcharge() {
    Scanner scanner = new Scanner(System.in);
    String line = scanner.nextLine().trim(); 
    String[] array = line.split(",");
    int n = array.length; 
    int[] coinsValues = new int[n];
    for (int i = 0; i<n ; i++) {
        coinsValues[i] = Integer.parseInt(array[i]);  
    }
    int total = scanner.nextInt(); 
    int[] coinNum = new int[total + 1];//存储1...money找零最少需要的硬币的个数  
    int[] coinValue = new int[total + 1];//最后加入的硬币，方便后面输出是哪几个硬币  
    coinNum[0] = 0; 
       for (int i = 1; i <= total; i++) {
            int minNum = i;//i面值钱，需要最少硬币个数
            int usedMoney = 0;//这次找零，在原来的基础上需要的硬币
            for (int j = 0; j < n; j++) {
                if (i >= coinsValues[j])//找零的钱大于这个硬币的面值
                {
                    if (coinNum[i - coinsValues[j]] + 1 <= minNum && (i == coinsValues[j] || coinValue[i - coinsValues[j]] != 0))//所需硬币个数减少了
                    {
                        minNum = coinNum[i - coinsValues[j]] + 1;//更新
                        usedMoney = coinsValues[j];//更新
                    }
                }
            }
            coinNum[i] = minNum;
            coinValue[i] = usedMoney;
        }
        System.out.print(coinNum[total]);
 }

```