省级门户网站建设,竞价推广教程,北京网站建设seo优化,中铁建设集团门户网门户1 子集和问题#xff08;Subset Sum Problem#xff09;
给定一组非负整数和一个值和#xff0c;确定给定集合中是否存在和等于给定和的子集。
示例#xff1a;
输入#xff1a;set[]{3#xff0c;34#xff0c;4#xff0c;12#xff0c;5#xff0c;2}#xff… 1 子集和问题Subset Sum Problem
给定一组非负整数和一个值和确定给定集合中是否存在和等于给定和的子集。
示例
输入set[]{33441252}sum9
输出真
有一个子集45和9。
输入设置[]{33441252}和30
输出False
没有加起来等于30的子集。
推荐做法
子集和问题
试试看
方法1递归。
方法对于递归方法我们将考虑两种情况。
考虑最后一个元素现在所需的总和目标总和–最后一个元素的值元素数量总元素–1
保留“最后一个”元素现在所需的总和目标总和元素数总元素数–1
以下是isSubsetSum问题的递归公式。
IsubSetSum集合n总和
IsubSetSum集合n-1总和| |
IsubSetSum集合n-1和集合[n-1]
基本情况
IsubSetSumsetnsumfalse如果sum0且n0
IsubSetSumsetnsum真如果sum0 2 源代码
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{public static bool SubsetSum_Problem_Solve(int[] set, int n, int sum){if (sum 0){return true;}if (n 0){return false;}if (set[n - 1] sum){return SubsetSum_Problem_Solve(set, n - 1, sum);}return SubsetSum_Problem_Solve(set, n - 1, sum) || SubsetSum_Problem_Solve(set, n - 1, sum - set[n - 1]);}public static bool SubsetSum_Problem_Solve_2th(int[] set, int n, int sum){bool[,] subset new bool[sum 1, n 1];for (int i 0; i n; i){subset[0, i] true;}for (int i 1; i sum; i){subset[i, 0] false;}for (int i 1; i sum; i){for (int j 1; j n; j){subset[i, j] subset[i, j - 1];if (i set[j - 1]){subset[i, j] subset[i, j] || subset[i - set[j - 1], j - 1];}}}return subset[sum, n];}public static bool SubsetSum_Problem_Solve_3th(int[] set, int n, int sum){int[,] tab new int[n 1, sum 1];for (int i 1; i n; i){for (int j 1; j sum; j){tab[i, j] -1;}}if (sum 0){return true;}if (n 0){return false;}if (tab[n - 1, sum] ! -1){return tab[n - 1, sum] 0;}if (set[n - 1] sum){tab[n - 1, sum] SubsetSum_Problem_Solve_3th(set, n - 1, sum) ? 1 : 0;return tab[n - 1, sum] 0;}else{if (SubsetSum_Problem_Solve_3th(set, n - 1, sum) || SubsetSum_Problem_Solve_3th(set, n - 1, sum - set[n - 1])){tab[n - 1, sum] 1;return true;}else{tab[n - 1, sum] 0;return false;}}}}
}3 源程序
using System; using System.Text; using System.Collections; using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm { public static partial class Algorithm_Gallery { public static bool SubsetSum_Problem_Solve(int[] set, int n, int sum) { if (sum 0) { return true; } if (n 0) { return false; } if (set[n - 1] sum) { return SubsetSum_Problem_Solve(set, n - 1, sum); } return SubsetSum_Problem_Solve(set, n - 1, sum) || SubsetSum_Problem_Solve(set, n - 1, sum - set[n - 1]); } public static bool SubsetSum_Problem_Solve_2th(int[] set, int n, int sum) { bool[,] subset new bool[sum 1, n 1]; for (int i 0; i n; i) { subset[0, i] true; } for (int i 1; i sum; i) { subset[i, 0] false; } for (int i 1; i sum; i) { for (int j 1; j n; j) { subset[i, j] subset[i, j - 1]; if (i set[j - 1]) { subset[i, j] subset[i, j] || subset[i - set[j - 1], j - 1]; } } } return subset[sum, n]; } public static bool SubsetSum_Problem_Solve_3th(int[] set, int n, int sum) { int[,] tab new int[n 1, sum 1]; for (int i 1; i n; i) { for (int j 1; j sum; j) { tab[i, j] -1; } } if (sum 0) { return true; } if (n 0) { return false; } if (tab[n - 1, sum] ! -1) { return tab[n - 1, sum] 0; } if (set[n - 1] sum) { tab[n - 1, sum] SubsetSum_Problem_Solve_3th(set, n - 1, sum) ? 1 : 0; return tab[n - 1, sum] 0; } else { if (SubsetSum_Problem_Solve_3th(set, n - 1, sum) || SubsetSum_Problem_Solve_3th(set, n - 1, sum - set[n - 1])) { tab[n - 1, sum] 1; return true; } else { tab[n - 1, sum] 0; return false; } } } } }
