C#，动态规划的集合划分问题（DP Partition problem）算法与源代码

1 动态规划问题中的划分问题

动态规划问题中的划分问题是确定一个给定的集是否可以划分为两个子集，使得两个子集中的元素之和相同。

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

2 应用示例


动态规划问题中的划分问题示例：
arr[]={1，5，11，5}
输出：真
数组可以划分为{1、5、5}和{11}
arr[]={1，5，3}
输出：false
数组不能划分为等和集。
以下是解决此问题的两个主要步骤：
1） 计算数组的和。如果sum为奇数，则不可能有两个sum相等的子集，因此返回false。
2） 如果数组元素之和为偶数，则计算sum/2并找到sum等于sum/2的数组子集。
第一步很简单。第二步很关键，可以使用递归或动态规划来解决。
递归解决方案
下面是上面提到的第二步的递归属性。
让isSubsetSum（arr，n，sum/2）为函数，如果
有一个子集arr[0..n-1]，其和等于和/2isSubsetSum问题可分为两个子问题
a） IsubSetSum（）不考虑最后一个元素（将n减至n-1）
b） isSubsetSum考虑最后一个元素（通过arr[n-1]和n到n-1减少sum/2）
如果上述任何子问题返回true，则返回true。
isSubsetSum（arr，n，sum/2）=isSubsetSum（arr，n-1，sum/2）|| isSubsetSum（arr，n-1，sum/2-arr[n-1]）

3 源代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public static partial class Algorithm_Gallery
	{
		#region 算法1
		private static bool Partition_Problem_IsSubset_Sum(int[] arr, int n, int sum)
		{
			if (sum == 0)
			{
				return true;
			}
			if (n == 0 && sum != 0)
			{
				return false;
			}
			if (arr[n - 1] > sum)
			{
				return Partition_Problem_IsSubset_Sum(arr, n - 1, sum);
			}

			return Partition_Problem_IsSubset_Sum(arr, n - 1, sum) || Partition_Problem_IsSubset_Sum(arr, n - 1, sum - arr[n - 1]);
		}

		static bool Partition_Problem_Solve(int[] arr, int n)
		{
			int sum = 0;
			for (int i = 0; i < n; i++)
			{
				sum += arr[i];
			}
			if (sum % 2 != 0)
			{
				return false;
			}
			return Partition_Problem_IsSubset_Sum(arr, n, sum / 2);
		}
		#endregion

		#region 算法2
		private static bool Partition_Problem_IsSubset_Sum(int[] arr, int n, int sum, int[,] dp)
		{
			if (sum == 0)
			{
				return true;
			}
			if (n == 0 && sum != 0)
			{
				return false;
			}
			if (dp[n, sum] != -1)
			{
				return true;
			}

			if (arr[n - 1] > sum)
			{
				return Partition_Problem_IsSubset_Sum(arr, n - 1, sum, dp);
			}

			dp[n, sum] = (Partition_Problem_IsSubset_Sum(arr, n - 1, sum, dp) || Partition_Problem_IsSubset_Sum(arr, n - 1, sum - arr[n - 1], dp)) ? 1 : -1;
			return dp[n, sum] > 0;
		}

		public static bool Partition_Problem_Solve_Second(int[] arr, int n)
		{
			int sum = 0;
			for (int i = 0; i < n; i++)
			{
				sum += arr[i];
			}
			if (sum % 2 != 0)
			{
				return false;
			}
			int[,] dp = new int[n + 1, sum + 1];

			return Partition_Problem_IsSubset_Sum(arr, n, sum / 2, dp);
		}
        #endregion

        #region 算法3
        public static bool Partition_Problem_Solve_Third(int[] arr, int n)
		{
			int sum = 0;
			for (int i = 0; i < n; i++)
			{
				sum += arr[i];
			}
			if (sum % 2 != 0)
			{
				return false;
			}

			bool[,] part = new bool[sum / 2 + 1, n + 1];
			for (int i = 0; i <= n; i++)
			{
				part[0, i] = true;
			}

			for (int i = 1; i <= sum / 2; i++)
			{
				part[i, 0] = false;
			}

			for (int i = 1; i <= sum / 2; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					part[i, j] = part[i, j - 1];
					if (i >= arr[j - 1])
					{
						part[i, j] = part[i, j - 1] || part[i - arr[j - 1], j - 1];
					}
				}
			}

			return part[sum / 2, n];
		}
        #endregion

        #region 算法4
        public static bool Partition_Problem_Solve_Fourth(int[] arr, int n)
		{
			int sum = 0;
			for (int i = 0; i < n; i++)
			{
				sum += arr[i];
			}
			if (sum % 2 != 0)
			{
				return false;
			}

			bool[] part = new bool[sum / 2 + 1];
			for (int i = 0; i <= sum / 2; i++)
			{
				part[i] = false;
			}

			for (int i = 0; i < n; i++)
			{
				for (int j = sum / 2; j >= arr[i]; j--)
				{
					if (part[j - arr[i]] == true || j == arr[i])
					{
						part[j] = true;
					}
				}
			}
			return part[sum / 2];
		}
		#endregion
	}
}

4 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class Algorithm_Gallery
    {
        #region 算法1
        private static bool Partition_Problem_IsSubset_Sum(int[] arr, int n, int sum)
        {
            if (sum == 0)
            {
                return true;
            }
            if (n == 0 && sum != 0)
            {
                return false;
            }
            if (arr[n - 1] > sum)
            {
                return Partition_Problem_IsSubset_Sum(arr, n - 1, sum);
            }

            return Partition_Problem_IsSubset_Sum(arr, n - 1, sum) || Partition_Problem_IsSubset_Sum(arr, n - 1, sum - arr[n - 1]);
        }

        static bool Partition_Problem_Solve(int[] arr, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += arr[i];
            }
            if (sum % 2 != 0)
            {
                return false;
            }
            return Partition_Problem_IsSubset_Sum(arr, n, sum / 2);
        }
        #endregion

        #region 算法2
        private static bool Partition_Problem_IsSubset_Sum(int[] arr, int n, int sum, int[,] dp)
        {
            if (sum == 0)
            {
                return true;
            }
            if (n == 0 && sum != 0)
            {
                return false;
            }
            if (dp[n, sum] != -1)
            {
                return true;
            }

            if (arr[n - 1] > sum)
            {
                return Partition_Problem_IsSubset_Sum(arr, n - 1, sum, dp);
            }

            dp[n, sum] = (Partition_Problem_IsSubset_Sum(arr, n - 1, sum, dp) || Partition_Problem_IsSubset_Sum(arr, n - 1, sum - arr[n - 1], dp)) ? 1 : -1;
            return dp[n, sum] > 0;
        }

        public static bool Partition_Problem_Solve_Second(int[] arr, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += arr[i];
            }
            if (sum % 2 != 0)
            {
                return false;
            }
            int[,] dp = new int[n + 1, sum + 1];

            return Partition_Problem_IsSubset_Sum(arr, n, sum / 2, dp);
        }
        #endregion

        #region 算法3
        public static bool Partition_Problem_Solve_Third(int[] arr, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += arr[i];
            }
            if (sum % 2 != 0)
            {
                return false;
            }

            bool[,] part = new bool[sum / 2 + 1, n + 1];
            for (int i = 0; i <= n; i++)
            {
                part[0, i] = true;
            }

            for (int i = 1; i <= sum / 2; i++)
            {
                part[i, 0] = false;
            }

            for (int i = 1; i <= sum / 2; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    part[i, j] = part[i, j - 1];
                    if (i >= arr[j - 1])
                    {
                        part[i, j] = part[i, j - 1] || part[i - arr[j - 1], j - 1];
                    }
                }
            }

            return part[sum / 2, n];
        }
        #endregion

        #region 算法4
        public static bool Partition_Problem_Solve_Fourth(int[] arr, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
            {
                sum += arr[i];
            }
            if (sum % 2 != 0)
            {
                return false;
            }

            bool[] part = new bool[sum / 2 + 1];
            for (int i = 0; i <= sum / 2; i++)
            {
                part[i] = false;
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = sum / 2; j >= arr[i]; j--)
                {
                    if (part[j - arr[i]] == true || j == arr[i])
                    {
                        part[j] = true;
                    }
                }
            }
            return part[sum / 2];
        }
        #endregion
    }
}
 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/439204.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于UDP实现直播间聊天的功能

基于UDP实现直播间聊天的功能

需求&#xff1a;软件划分为用户客户端和主播服务端两个软件client.c和server.c 用户客户端负责&#xff1a;1.接收用户的昵称2.接收用户输入的信息&#xff0c;能够将信息发送给服务端3.接收服务端回复的数据信息,并完成显示主播服务端负责&#xff1a;1.对所有加入直播间的用…
阅读更多...
无尘车间：保障电子产品品质与员工健康

无尘车间：保障电子产品品质与员工健康

在当今数字化时代&#xff0c;电子产品已经成为我们生活中不可或缺的一部分。从智能手机到计算机&#xff0c;从家用电器到汽车电子系统&#xff0c;电子产品无处不在&#xff0c;给我们的生活带来了便利与快捷。然而&#xff0c;这些高科技产品的背后是一系列复杂的制造过程&a…
阅读更多...
Paddle上手实战——NLP经典cls任务“推特文本情感13分类”

Paddle上手实战——NLP经典cls任务“推特文本情感13分类”

Paddle上手实战——NLP经典cls任务“推特文本情感13分类” 实战背景介绍 数据地址：https://www.heywhale.com/home/activity/detail/611cbe90ba12a0001753d1e9/content Twitter推文具备多重特性，首要之处在于其与Facebook的显著区别——其完全基于文本形式，通过Twitter接…
阅读更多...
基于docker安装的Jenkins实现python执行自动化测试程序

基于docker安装的Jenkins实现python执行自动化测试程序

背景 通过Jenkins实现自动化测试，在全局配置中配置好后，执行构建发生如下错误 解决办法: 在Jenkins中插件管理中下载python后，回到Jenkins容器中 查找刚下载的python所在位置 到Jenkins中全局配置中修改脚本 1.可以在环境变量中定义python所在位置 2.在一下图示中进行获取…
阅读更多...
Rust泛型与trait特性，模仿接口的实现

Rust泛型与trait特性，模仿接口的实现

泛型是一个编程语言不可或缺的机制。 C 语言中用"模板"来实现泛型&#xff0c;而 C 语言中没有泛型的机制&#xff0c;这也导致 C 语言难以构建类型复杂的工程。 泛型机制是编程语言用于表达类型抽象的机制&#xff0c;一般用于功能确定、数据类型待定的类&#xf…
阅读更多...
VMware Workstation安装Linux虚拟机与虚拟机克隆，特别适合搭建虚拟机集群环境，工作效率直线上升~

VMware Workstation安装Linux虚拟机与虚拟机克隆，特别适合搭建虚拟机集群环境，工作效率直线上升~

虚拟机 一、安装虚拟机二、克隆虚拟机三、配置静态IP地址一、安装虚拟机 设置虚拟机名称与安装位置 设置磁盘大小 配置硬件参数
阅读更多...
Redis主从架构和管道Lua(一)

Redis主从架构和管道Lua(一)

Redis主从架构 架构 Redis主从工作原理 如果为master配置了一个slave,不管这个slave是否是第一次连接上Master,它都会发送一个PSYNC命令给master请求复制数据。master受到PSYNC命令&#xff0c;会在后台进行数据持久化通过bgsave生成最新的 RDB快照文件&#xff0c;持久化期间…
阅读更多...
Linux阻塞与非阻塞IO简介

Linux阻塞与非阻塞IO简介

一. 简介 阻塞与非阻塞IO是Linux驱动开发中很常见的两种设备访问模式&#xff0c;在编写驱动的时候&#xff0c;一定要考虑到阻塞和非阻塞。 本文来学习一下&#xff0c;什么是 Linux下的阻塞与非阻塞IO访问。 二. Linux阻塞与非阻塞IO 这里的 “IO” 并不是我们学习 STM32…
阅读更多...
[机器视觉]halcon十二 条码识别、字符识别之字符识别

[机器视觉]halcon十二 条码识别、字符识别之字符识别

[机器视觉]halcon十二 条码识别、字符识别之字符识别 流程 获取图像-》创建模型-》查找文本-》清除模型 效果 算子 create_text_model_reader &#xff1a; 创建文本模型 find_text : 查找文本 get_text_result &#xff1a;获取文本内容 set_text_model_param : 设置文本模板…
阅读更多...
使用Pytorch导出自定义ONNX算子

使用Pytorch导出自定义ONNX算子

在实际部署模型时有时可能会遇到想用的算子无法导出onnx&#xff0c;但实际部署的框架是支持该算子的。此时可以通过自定义onnx算子的方式导出onnx模型&#xff08;注&#xff1a;自定义onnx算子导出onnx模型后是无法使用onnxruntime推理的&#xff09;。下面给出个具体应用中的…
阅读更多...
米酒生产加工污水处理需要哪些工艺设备

米酒生产加工污水处理需要哪些工艺设备

米酒生产加工过程中产生的污水是一项重要的环境问题&#xff0c;需要采用适当的工艺设备进行处理。下面将介绍一些常用的污水处理工艺设备。 首先&#xff0c;生产过程中的污水需要进行初级处理&#xff0c;常见的设备包括格栅和砂池。格栅用于去除污水中的大颗粒杂质&#xff…
阅读更多...
python导出数据到sqlite中

python导出数据到sqlite中

import sqlite3# 数据 data [{username: 张三, age: 33, score: 13},{username: 李四, age: 44, score: 14},{username: 王五, age: 55, score: 15}, ]# 连接SQLite数据库&#xff08;如果不存在则创建&#xff09; conn sqlite3.connect(test.db)# 创建游标对象 cursor con…
阅读更多...
神经网络8-注意力机制

神经网络8-注意力机制

注意力机制&#xff08;Attention Mechanism&#xff09;源于对人类视觉的研究。在认知科学中&#xff0c;由于信息处理的瓶颈&#xff0c;人类会选择性地关注所有信息的一部分&#xff0c;同时忽略其他可见的信息。这种机制被称为注意力机制。举个例子来说&#xff0c;当我们观…
阅读更多...
【排序算法】深入理解插入排序算法：从原理到实现

【排序算法】深入理解插入排序算法：从原理到实现

1. 引言 排序算法是计算机科学中的基本问题之一&#xff0c;它的目标是将一组元素按照某种规则进行排列。插入排序是其中一种简单但有效的排序算法&#xff0c;通过逐步构建有序序列来实现排序。本文将从原理、时间复杂度、应用场景、优缺点等方面深入探讨插入排序算法&#x…
阅读更多...
keepalived原理以及lvs、nginx跟keeplived的运用

keepalived原理以及lvs、nginx跟keeplived的运用

keepalived基础 keepalived的原理是根据vrrp协议&#xff08;主备模式&#xff09;去设定的 vrrp技术相关原理 状态机&#xff1b; 优先级0~255 心跳线1秒 vrrp工作模式 双主双备模式 VRRP负载分担过程 vrrp安全认证&#xff1a;使用共享密匙 keepalived工具介绍 keepal…
阅读更多...
如何压缩图片大小到100kb以下？

如何压缩图片大小到100kb以下？

如何压缩图片大小到100kb以下&#xff1f;不知道上班族小伙伴有没有发现&#xff0c;当我们工作中使用图片的时候经常遇到遇到一个尴尬的情况&#xff0c;例如我们需要网某个网站上传一张图片的时候&#xff0c;会被限制要求图片大小不能超过100kb&#xff0c;如果超过就无法进…
阅读更多...
基于uniapp cli项目开发的老项目，运行报错path.replace is not a function

基于uniapp cli项目开发的老项目，运行报错path.replace is not a function

项目&#xff1a;基于uniapp cli的微信小程序老项目 问题&#xff1a;git拉取代码&#xff0c;npm安装包时就报错&#xff1b; cnpm能安装成功包&#xff0c;运行报错 三种方法尝试解决&#xff1a; 更改代码&#xff0c;typeof pathstring的话&#xff0c;才走path.replace…
阅读更多...
JVM 面试题

JVM 面试题

1、什么情况下会发生栈内存溢出。 栈内存溢出通常发生在以下几种情况中&#xff1a; 函数递归调用过深&#xff1a; 当函数递归调用自身且没有合适的退出条件时&#xff0c;每次递归调用都会在栈上分配一个新的栈帧来存储局部变量、返回地址等信息。如果递归层次过多&#xff…
阅读更多...
计讯物联山体滑坡地质灾害监测方案为灾区保驾护航

计讯物联山体滑坡地质灾害监测方案为灾区保驾护航

针对我国某些地区频繁爆发山体滑坡的情况&#xff0c;计讯物联深入调研滑坡体自动监测、无线通讯、险情预报等方面&#xff0c;自主研发反应快速高效、可广泛应用的山体滑坡地质灾害监测方案&#xff0c;全面掌握山体滑坡信息&#xff0c;为当地居民留有余裕的逃生时间。 计讯物…
阅读更多...
Docker 配置阿里云镜像加速器

Docker 配置阿里云镜像加速器

一、首先需要创建一个阿里云账号 二、登录阿里云账号 三、进入控制台 四、搜索容器镜像服务&#xff0c;并选择 五、选择镜像工具中的镜像加速 六 、配置镜像源 注意&#xff1a;有/etc/docker文件夹的直接从第二个命令开始
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站