问题描述中的数据题如何判断子集和问题是否存在S的一个子集S1，使得子集S1等于c？
答案:2 悬赏:40 手机版
解决时间 2021-02-18 23:20
- 提问者网友：谁的错
- 2021-02-18 16:11
问题描述中的数据题如何判断子集和问题是否存在S的一个子集S1，使得子集S1等于c？
最佳答案
- 五星知识达人网友：忘川信使
- 2021-02-18 17:24
给定n 个整数的集合X={x1，x2，...，xn}和一个正整数y，编写一个回溯算法，
在X中寻找子集Yi，使得Yi中元素之和等于y。
#include#include
int len; // 输入长度.
int sum; // 和.
int *data; // 数据.
char *output; // 所求子集元素，与输入数据对应，'Y'为取.
// 获取输入.
void GetInput(){
int i;
printf("输入集合个数: ");
scanf("%d", &len);
while(len <= 0){
printf("集合个数必须大于0: ");
scanf("%d", &len);
}
data = new int[len];
output = new char[len];
for(i = 0; i < len; i++){
printf("输入第%d个数: ", i+1);
scanf("%d", &data[i]);
output[i] = 'N';
}
printf("输入子集和: ");
scanf("%d", &sum);
while(sum <= 0){
printf("子集和必须大于0: ");
scanf("%d", &len);
}
}
// 回朔求解:有解返回非0值，无解返回0.
int GetRes(){
int p = 0; // 指向当前值.
int temp = 0; // 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y';
temp += data[p];
if(temp == sum){
return 1;
}
else if(temp > sum){
output[p] = 'N';
temp -= data[p];
}
p++;
}
if(p >= len){
// 开始回朔.
while('Y' == output[p-1]){
p--;
output[p] = 'N';
temp -= data[p];
if(p < 1){
return 0;
}
}
while('N' == output[p-1]){
p--;
if(p < 1){
return 0;
}
}
output[p-1] = 'N';
temp -= data[p-1];
}
}
return 0;
}
// 打印结果.
void PrintRes(){
int i;
在X中寻找子集Yi，使得Yi中元素之和等于y。
#include
int len; // 输入长度.
int sum; // 和.
int *data; // 数据.
char *output; // 所求子集元素，与输入数据对应，'Y'为取.
// 获取输入.
void GetInput(){
int i;
printf("输入集合个数: ");
scanf("%d", &len);
while(len <= 0){
printf("集合个数必须大于0: ");
scanf("%d", &len);
}
data = new int[len];
output = new char[len];
for(i = 0; i < len; i++){
printf("输入第%d个数: ", i+1);
scanf("%d", &data[i]);
output[i] = 'N';
}
printf("输入子集和: ");
scanf("%d", &sum);
while(sum <= 0){
printf("子集和必须大于0: ");
scanf("%d", &len);
}
}
// 回朔求解:有解返回非0值，无解返回0.
int GetRes(){
int p = 0; // 指向当前值.
int temp = 0; // 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y';
temp += data[p];
if(temp == sum){
return 1;
}
else if(temp > sum){
output[p] = 'N';
temp -= data[p];
}
p++;
}
if(p >= len){
// 开始回朔.
while('Y' == output[p-1]){
p--;
output[p] = 'N';
temp -= data[p];
if(p < 1){
return 0;
}
}
while('N' == output[p-1]){
p--;
if(p < 1){
return 0;
}
}
output[p-1] = 'N';
temp -= data[p-1];
}
}
return 0;
}
// 打印结果.
void PrintRes(){
int i;
printf("
所求子集为: ");for(i = 0; i < len; i++){
if('Y' == output[i]){
printf("%d ", data[i]);
}
}
}
void main(){
GetInput();
if(GetRes()){
PrintRes();
}
else{
printf("无解！");
}
printf("
Press any key to continue.");getch();
}
全部回答
- 1楼网友：你哪知我潦倒为你
- 2021-02-18 18:10
给定n 个整数的集合X={x1，x2，...，xn}和一个正整数y，编写一个回溯算法，
在X中寻找子集Yi，使得Yi中元素之和等于y。
#include#include
int len; // 输入长度.
int sum; // 和.
int *data; // 数据.
char *output; // 所求子集元素，与输入数据对应，'Y'为取.
// 获取输入.
void GetInput(){
int i;
printf("输入集合个数: ");
scanf("%d", &len);
while(len <= 0){
printf("集合个数必须大于0: ");
scanf("%d", &len);
}
data = new int[len];
output = new char[len];
for(i = 0; i < len; i++){
printf("输入第%d个数: ", i+1);
scanf("%d", &data[i]);
output[i] = 'N';
}
printf("输入子集和: ");
scanf("%d", &sum);
while(sum <= 0){
printf("子集和必须大于0: ");
scanf("%d", &len);
}
}
// 回朔求解:有解返回非0值，无解返回0.
int GetRes(){
int p = 0; // 指向当前值.
int temp = 0; // 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y';
temp += data[p];
if(temp == sum){
return 1;
}
else if(temp > sum){
output[p] = 'N';
temp -= data[p];
}
p++;
}
if(p >= len){
// 开始回朔.
while('Y' == output[p-1]){
p--;
output[p] = 'N';
temp -= data[p];
if(p < 1){
return 0;
}
}
while('N' == output[p-1]){
p--;
if(p < 1){
return 0;
}
}
output[p-1] = 'N';
temp -= data[p-1];
}
}
return 0;
}
// 打印结果.
void PrintRes(){
int i;
printf("\r\n所求子集为: ");
for(i = 0; i < len; i++){
if('Y' == output[i]){
printf("%d ", data[i]);
}
}
}
void main(){
GetInput();
if(GetRes()){
PrintRes();
}
else{
printf("无解！");
}
printf("\r\nPress any key to continue.");
getch();
}
在X中寻找子集Yi，使得Yi中元素之和等于y。
#include
int len; // 输入长度.
int sum; // 和.
int *data; // 数据.
char *output; // 所求子集元素，与输入数据对应，'Y'为取.
// 获取输入.
void GetInput(){
int i;
printf("输入集合个数: ");
scanf("%d", &len);
while(len <= 0){
printf("集合个数必须大于0: ");
scanf("%d", &len);
}
data = new int[len];
output = new char[len];
for(i = 0; i < len; i++){
printf("输入第%d个数: ", i+1);
scanf("%d", &data[i]);
output[i] = 'N';
}
printf("输入子集和: ");
scanf("%d", &sum);
while(sum <= 0){
printf("子集和必须大于0: ");
scanf("%d", &len);
}
}
// 回朔求解:有解返回非0值，无解返回0.
int GetRes(){
int p = 0; // 指向当前值.
int temp = 0; // 当前子集合和.
while(p >= 0){
if('N' == output[p]){
// 选中当前项.
output[p] = 'Y';
temp += data[p];
if(temp == sum){
return 1;
}
else if(temp > sum){
output[p] = 'N';
temp -= data[p];
}
p++;
}
if(p >= len){
// 开始回朔.
while('Y' == output[p-1]){
p--;
output[p] = 'N';
temp -= data[p];
if(p < 1){
return 0;
}
}
while('N' == output[p-1]){
p--;
if(p < 1){
return 0;
}
}
output[p-1] = 'N';
temp -= data[p-1];
}
}
return 0;
}
// 打印结果.
void PrintRes(){
int i;
printf("\r\n所求子集为: ");
for(i = 0; i < len; i++){
if('Y' == output[i]){
printf("%d ", data[i]);
}
}
}
void main(){
GetInput();
if(GetRes()){
PrintRes();
}
else{
printf("无解！");
}
printf("\r\nPress any key to continue.");
getch();
}
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯