《0-1 背包问题》

 1 package com.zuoyan.packageproblem;
 2 
 3 import java.util.Scanner;
 4 
 5 public class Main {
 6 
 7     public static final int I =100;
 8     public static final int J =100;
 9     public static int goodCount;
10     public static int capacity;
11     public static int V[][] = new int [I][J];
12     public static int weight[] = new int [I];
13     public static int value [] = new int [I];
14     
15     
16     public static void main(String[] args) {
17 
18         Scanner in = new Scanner(System.in);
19         goodCount = in.nextInt();
20         capacity = in.nextInt();
21         
22         for(int i = 1;i<=goodCount;i++)
23         {
24             weight[i] = in.nextInt();
25             value [i] = in.nextInt();
26         }
27         
28         int maxValue = FinaMax();
29         System.out.println(maxValue);
30         
31     }
32     
33     public static int FinaMax(){
34         for(int i = 1;i<=goodCount;i++)
35         {
36             for(int j = 1;j<=capacity;j++)
37             {
38                 //分两种情况   
39                 //1.当前背包容量不能放进当前商品
40                 if(weight[i]>j)
41                 {
42                     V[i][j]=V[i-1][j];
43                 }
44                 //2.当期背包容量大于当前商品的重量
45                 else{
46                     //不装当前商品价值最大
47                     if(V[i-1][j]>(V[i-1][j-weight[i]]+value[i]))
48                     {
49                         V[i][j] = V[i-1][j];
50                     }
51                     //装上当前商品价值最大
52                     else{
53                         V[i][j] = V[i-1][j-weight[i]]+value[i];
54                     }
55                 }
56             }
57         }
58         return V[goodCount][capacity];
59     }
60     
61 }