小易的考试成绩（0 -1背包问题）

小易的考试成绩（0 -1背包问题）

小易参加了一次考试，这场包含 n 个题目，第 i 个题目的分数是 si 。
如果小易第 i 题目回答正确，他将得到 Si 分，否则该题目他将得到 0 分。
最终的考试得分是所有题目得分的总和。
由于阅卷老师很讨厌数字 5，在阅卷时如果一个学生的考试总分中含有数字 5，那么阅卷老师将气愤地给他 0 分。
那么小易考试的最高得分是多少？
输入描述:
输入的第一行是正整数 n(1<=n<=100) ，代表这场考试的题目数。
接下一行含有n个正整数 s1,s2,s3…sn (1<= si <=200)
输出描述:
输出一个整数，代表小易考试的最高得分。
示例1
输入
5
5 15 5 15 5
输出
40
说明
如果所有题目都答对，总分为45，但里面包含了数字5,所以最高得分应该为40
示例2
输入
5
5 15 5 15 8
输出
48
示例3
输入
1
5
输出
0

直接0-1背包问题

package niuke.wangyi_2021;

import java.util.Scanner;

public class Main_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] res = new int[n];
        for(int i = 0 ; i < n ; i++)
        {
            res[i] = scanner.nextInt();
        }
        new Main_2().search(res);
    }
    private void search(int[] res )
    {
        int max1 = 0;
        for(int i = 0 ; i < res.length ; i++)
        {
            max1 += res[i];
        }
        if(pan(max1))
        {
            System.out.println(max1);
            return;
        }
        boolean[] result = new boolean[max1 + 1];
        result[0] = true;
        for(int i = 0 ; i < res.length ; i++ )
        {

            for(int j = max1 ; j >= res[i] ; j--)
            {
                if(result[j])
                    continue;
                if(result[j - res[i]]){
                    result[j] = true;
                }
            }
        }
        for(int i = max1 ; i >= 0; i--)
        {
            if(result[i] && pan(i))
            {
                System.out.print(i);
                return;
            }
        }
    }
    private boolean pan(int n)
    {
        if(String.valueOf(n).contains("5"))
            return false;
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58