题目

小易的幸运数字是7，现有一个整数数组 nums，请你找出并返回能被七整除的子集合的最大和，如果找不到则返回-1。

输入描述:
一个正整数数组列表nums，用空格区分，1<=length(nums)<=100000，sum(nums) <= 1000000000

输出描述:
一个整数，最大和

思路

使用动态规划 0-1背包。
dp[i] = 1 表明 和为i的是存在的。
dp[i] = 0 表明 和为i是不存在的（初始化的值）

1. 将数组中每一个数 的dp设为 1
2. 0 和sum总和的dp设为1
3. 对于每一个 从sum 可以减去 数组数 的dp设为1（也是j从sum 再–的原因，相当于一个一个数减）

从sum往下遍历，找到第一个 dp为1 且满足 整除7 的，则为返回值。

代码

import java.util.Scanner;public class Main {// 除7余数问题 01背包 看哪些数满足public static void main(String[] args) {Scanner sc = new Scanner(System.in);String inputStr = sc.nextLine();String[] inputs = inputStr.split(" ");int[] nums = new int[inputs.length];int sum = 0;for(int i=0;i<inputs.length;i++) {nums[i] = Integer.parseInt(inputs[i]);sum = sum+nums[i];}int res = getMax(nums, sum);System.out.println(res);}public static int getMax(int[] nums, int sum) {// 先对每一个求和，和dp设置为trueint[] dp = new int[sum+1];dp[0] = 1;dp[sum] = 1;for(int i=0;i<nums.length;i++) {dp[nums[i]] = 1;for (int j=sum;j>=0;j--) {if(dp[j] == 1 && j>nums[i]) {dp[j-nums[i]] =1; // 已经减过其他数的j，是有的，再减下这个数，也是有的}}}// 倒序找最大for(int z=sum;z>=0;z--) {if(dp[z] == 1 && z%7==0) {return z;}}return -1;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！