子集和问题
描述 Description
【问题描述】
子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。
【编程任务】
对于给定的正整数的集合S={ x1， x2，…， xn}和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。
【输入格式】
由文件subsum.in提供输入数据。文件第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
【输出格式】
程序运行结束时，将子集和问题的解输出到文件subsum.out中。当问题无解时，输出“No Solution!”。
【输入样例】
5 10
2 2 6 5 4
【输出样例】
2 2 6
思路：
emmmmm，第一反应就是这个问题和求子集问题神似,用递归回溯来做，于是我就写了一个求子集的外加一个判定，最后超时了，然后再想觉得有点像01背包，于是我试着写了一个，发现动态方程我写不出来，因为这个是固定和，和01背包不一样，所以gg，然后我看了别人的想法，有个是用非递归回溯做的，这里贴一下代码：
#include<stdio.h>
#define MAX 10000
int data[MAX];
bool v[MAX];
int n, c;
bool traceback(int n) {
int p = 0, sum = 0;
while (p >= 0)
{
if (!v[p])
{
v[p] = true;
sum += data[p];
if (c == sum)
return true;
else if (c < sum)
{
v[p] = false;
sum -= data[p];
}
p++;
}
if (p >= n)
{
while (v[p - 1])
{
p--;
v[p] = false;
if (p<1) return false;
}
while (!v[p - 1])
{
p--;
if (p<1) return false;
}
sum -= data[p - 1];
v[p - 1] = false;
}
}
return false;
}
int main() {
scanf("%d %d", &n, &c);
for (int i = 0; i < n; i++)
scanf("%d", &data[i]);
if (traceback(n))
{
int first = 1;
for (int i = 0; i < n; i++)
if (v[i])
{
if (first)
first = 0;
else
printf(" ");
printf("%d", data[i]);
}
printf("\n");
}
else
printf("No Solution!\n");
return 0;
}
解释：它的思想是，从第一个元素开始，如果此时当前的元素不在集合内的话，将这个元素加到子集当中来（用visited数组标记） ，将sum加上这个元素的值。然后判断如果sum恰好为目标值c的话，就返回正值并且打印结果。如果sum > c 的话则舍弃当前这个元素，修改标记数组，并且将sum减去这个元素的值。只要还有元素没有判断就继续选择。直到第n个元素，如果第n个元素判断完还没有找到解的话，就回溯到上一次选择的那个点，将其从集合里面删除并从它后一个点继续重复前面的操作。如果回溯的时候回溯到了第一个元素之前的话呢，表示这个时候要么所有元素都加入到集合都不够，或者是所有的情况都找过了还是没有解决方案，这个时候返回无解。
摘自：http://blog.sina.com.cn/s/blog_7865b083010100dd.html
----------------------------------------------2018.3.10更新-------------------------------------------
這从我用了背包的想法又把这个题做了一遍，因为找不到之前 的题目了，所以就自己简答的测了几组数据，如果大家有发现我的错误，请务必指正，谢谢.
思路：
我之前就在想这个提和01背包神似，所以我就一直想用01来做，一直被困在如何输出，我输出所有的表之后发现，从最后一位每次往上一个状态推就可以找到一个符合题目要求的解。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1024;
int dp[MAX][MAX];
int p[MAX];
int n,m;
int main(void) {
cin >> m >> n;
for (int i = 1; i <= m; i++)
cin >> p[i];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (i == 1 ? 0 : dp[i - 1][j]);
if (j >= p[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - p[i]] + p[i]);
}
}
}
for (int i = 0; i <= m; i++) {//打印所有关系表格
for (int j = 0; j <= n; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (int i = m; i > 0; i--) {//从最后一位往前获取
for(int j=0;j<=n;j++){
if (dp[i][n] - p[i] == dp[i - 1][j]) {
cout << p[i] << " ";
n = j;
}
}
}
system("pause");
return 0;
}
----------------------------------------------2019.8.30更新-------------------------------------------
突然诈尸看了博客发现有留言说第一份代码不对，测试了发现还真的有问题，但当时oj直接ac了，可能是oj的测试点太少没有囊括这种情况，所以又想了下，我认为是在回溯的时候，sum和没有减去当前值，导致的最后求得序列不对，因此解决办法是在第29行后面插入一句，意思是如果当前点是访问过的，将其访问位置为未访问并且sum减去当前下标为访问点的data值。
if(p>1)sum-=data[p];
这是我目前想到的解决办法，然后自己测试了几组数据发现没什么毛病，如果有老铁发现还有错误请指出来，我会继续改进这份代码。