每日OJ题_牛客_DP45分割等和子集_动态规划_C++_Java

目录

牛客_DP45分割等和子集_动态规划

题目解析

C++代码

Java代码

---

牛客_DP45分割等和子集_动态规划

孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网

描述：

        给定一个只包含正整数的数组 nums ，请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。

数据范围： 1≤n≤500  ， 数组中的元素满足 1≤numsi​≤100 

输入描述：

第一行输入一个正整数 n ，表示数组 nums 的长度。

第二行输入 n 个正整数，表示数组中的值。

输出描述：

如果满足题目条件，输出 true ，否则输出 false

---

题目解析

01 背包问题：原问题转换成，从 n 个数中选，总和恰好为 sum / 2，能否挑选出来。

        思路转移：从一个数组中取数字，每个数字只能取一次，问取出的数字之和与未取出的数字之和能否相等。 分析：一个数组中的所有数字分为两部分，问两部分的和能否相等，很明显，如果整个数组的和(s)是奇数，必然不能。当为偶数，则判断是否能在数组中取出一些数，使得它们的和为s/2。

        这样问题转移为：容量为sum /2的背包，nums保存多个物品的重量，每个物品仅有一个，问能否把背包装满？ dp[i]表示 当容量为i时，背包能最多装多重的物品。答案就是dp[sum /2]==sum /2，当容量为sum /2时，看最大能装重量是否是sum ​​​​​​​/2? 转移：dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])，当j>=nums[i]时。 先遍历物品，再遍历容量：

C++代码

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> nums(n + 1);int sum = 0;for(int i = 1; i <= n; ++i){cin >> nums[i];sum += nums[i];}if(sum % 2 == 1){cout << "false" << endl;return 0;}sum /= 2;vector<int> dp(sum + 1); // 滚动数组优化for(int i = 1; i <= n; ++i){for(int j = sum; j >= nums[i]; --j){dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);if(dp[j] == sum){cout << "true" << endl;return 0;}}}cout << "false" << endl;return 0;
}// #include <iostream>
// #include <vector>
// using namespace std;// int main()
// {
//     int n = 0;
//     cin >> n;
//     vector<int> nums(n + 1);
//     int sum = 0;
//     for(int i = 1; i <= n; ++i)
//     {
//         cin >> nums[i];
//         sum += nums[i];
//     }
//     if(sum % 2 == 1)
//     {
//         cout << "false" << endl;
//         return 0;
//     }
//     sum /= 2;
//     vector<vector<int>> dp(n + 1, vector<int>(sum + 1));
//     for(int i = 1; i <= n; ++i)
//     {
//         for(int j = 0; j <= sum; ++j)
//         {
//             dp[i][j] = dp[i - 1][j];
//             if(j >= nums[i])
//                 dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]] + nums[i]);
//             if(dp[i][j] == sum)
//             {
//                 cout << "true" << endl;
//                 return 0;
//             }
//         }
//     }
//     cout << "false" << endl;
//     return 0;
// }

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static int N = 510, M = 510 * 110 / 2;public static int n;public static int[] arr = new int[N];public static boolean[][] dp = new boolean[N][M];public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();int sum = 0;for(int i = 1; i <= n; i++){arr[i] = in.nextInt();sum += arr[i];}if(sum % 2 == 1){System.out.println("false");}else{sum /= 2;dp[0][0] = true;for(int i = 1; i <= n; i++){for(int j = 0; j <= sum; j++){dp[i][j] = dp[i - 1][j];if(j >= arr[i]){dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i]];}}}if(dp[n][sum])System.out.println("true");elseSystem.out.println("false");}}
}