《01-背包问题-点菜》

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4     
 5     //身上拥有的钱
 6     private static int M;
 7     //拥有的测试用例
 8     private static int N;
 9     //用例记录每道菜的价格
10     private static int [] array =new  int [1001];
11     //记录方案
12     private static int [][] V = new int [1001][1001];
13     
14     
15     public static void main(String[] args) {
16         
17         Scanner in = new Scanner(System.in);
18         N = in.nextInt();
19         M = in.nextInt();
20         for(int i = 1;i<=N;i++)
21         {
22             array[i] = in.nextInt();
23         }
24         FindTotal();
25         
26     }
27     
28     public static void FindTotal()
29     {
30         for(int i = 1;i<=N;i++)
31         {
32             for(int j = 1;j<=M;j++){
33                 //如果钱刚好够用  方案总数等于  没有这个菜品时候的方案总数+1
34                 if(j==array[i]){
35                     V[i][j]=V[i-1][j]+1;
36                 }
37                 
38                 //如果钱够用的话，总的方案数目  等于吃这道菜的方案数目+不吃这道菜的方案数目
39                 if(j>array[i]){
40                     V[i][j] = V[i-1][j]+V[i-1][j-array[i]];
41                 }
42                 
43                 //如果钱不够用的情况 、等于不选这道菜的所有情况
44                 if(j<array[i]){
45                     V[i][j] = V[i-1][j];
46                 }
47             }
48         }
49         
50         System.out.println(V[N][M]);
51     }
52 
53 }