首页 > 其他分享 >求解幂集问题、简单0/1背包问题

求解幂集问题、简单0/1背包问题

时间:2023-10-25 22:33:48浏览次数:29  
标签:ps 幂集 背包 求解 int 穷举法 vector 集合

一、幂集问题

1.1 问题描述

  对于给定的正整数n(n>=1),求1-n构成的集合的幂集(即由1-n的集合中所有自己构成的集合,包括全集和空集)。

1.2 求解思路与代码

1、直接穷举法:将1-n存放到数组a中,用b数组中1-n的元素来标记(0为不在当前集合,1为在当前集合),此时便可将问题转化为:例如,n=3,幂集便是000-111每个数中1对应的数字所组成的集合,只需要将b数组从000变换到111共七次。具体过程如下:

具体代码如下:

#include<iostream>
#include<math.h>
#define MaxN 10
using namespace std;

//直接穷举法(根据二进制位求解,每次加1,输出1对应的数字)

void inc(int b[], int n) {		//将b表示的二进制数增1
	for (int i = 0; i < n; i++) {//遍历数组b
		if (b[i]) b[i] = 0;		//进位时,1变为0,继续对下一位进行进1
		else {
			b[i] = 1;			//0直接变成1
			break;
		}
	}
}

void PSet(int a[], int b[], int n) {
	int i, k;
	int pw = (int)pow(2, n);	//要进行2^n次方次
	cout << "1-" << n << "的幂集:" << endl;
	for (i = 0; i < pw; i++) {
		cout << "{";
		for (k = 0; k < n; k++) {//输出1对应的数字
			if (b[k]) {
				cout << a[k];
			}
		}
		cout << "} ";
		inc(b, n);
	}
}

int main() {
	int n = 3;
	int a[MaxN], b[MaxN];
	for (int i = 0; i < n; i++) {
		a[i] = i + 1;
		b[i] = 0;
	}
	PSet(a, b, n);
    return 0;
}

2、增量穷举法:即首先定义一个空集,和装所有幂集的大集合,每次向所有空集和有元素的集合中添加新的元素,并将添加后的集合放在大集合的后面,具体过程如下:

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> ps;
//增量穷举法

void Pset(int n) {
	vector<vector<int>> ps1;
	vector<vector<int>>::iterator it;
	vector<int> s;		//定义一个空集合并添加到ps中
	ps.push_back(s);
	for (int i = 1; i <= n; i++) {
		ps1 = ps;
		for (it = ps1.begin(); it != ps1.end(); ++it) {//将i添加到当前有的集合元素中
			(*it).push_back(i);
		}
		for (it = ps1.begin(); it != ps1.end(); ++it) {//将被添加的集合元素添加到ps中
			ps.push_back(*it);
		}
	}
}

void Dispps() {		//输出幂集
	vector<vector<int>>::iterator it;
	vector<int>::iterator sit;
	for (it = ps.begin(); it != ps.end(); ++it) {
		cout << "{";
		for (sit = (*it).begin(); sit != (*it).end(); ++sit) {
			cout << *sit;
		}
		cout << "} ";
	}
}

int main() {
	int n = 3;
	Pset(n);
	cout << "1-" << n << "的幂集:" << endl;
	Dispps();
	return 0;
}

二、简单0/1背包问题

2.1 问题描述

  有n个重量分别为w1,w2,......,wn的物品(编号1~n),它们的价值分别为v1,v2,......vn,给定一个容量为W的背包。设计从这些物品中选取一部分物品放入该背包的方案,每个物品要么选中要么不选中(每个物品只能取0或1次),要求选中的物品不仅能够放到背包中,而且具有最大的价值。例:根据下表所示的4个物品求出W=6的所有解和最佳解。

2.2 问题求解

  求所有解,先找问题所有解空间;求最佳解,在求所有解期间保存最佳解。此题解空间为四个物品所组成的全部集合(2^4=16个解),将每个集合的重量和价值加起来并保存在一个变量中,每次与最佳解相比较,看是否有更好的解。由此,可以仿照求解幂集问题,先使用二维数组按照物品编号组成集合,使用增量穷举法,将所有解空间存放在二维数组中,最后将其取出进行比较。具体代码如下:

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> ps;		//幂集,存放所有子域

void PSet(int n) {			//按照物品的编号求出所有子域并添加到幂集中
	vector<vector<int>> ps1;
	vector<vector<int>>::iterator it;
	vector<int> s;
	ps.push_back(s);
	for (int i = 1; i <= n; i++) {//增量穷举法
		ps1 = ps;
		for (it = ps1.begin(); it != ps1.end(); ++it) {
			(*it).push_back(i);
		}
		for (it = ps1.begin(); it != ps1.end(); ++it) {
			ps.push_back(*it);
		}
	}
}

void KNap(int w[], int v[], int W) {
	int count = 0;						//第count求解方案
	int sumw, sumv;						//和重量,价值
	int maxi=1, maxw=0, maxv=0;				//最优解
	vector<vector<int>>::iterator it;	//幂集迭代器
	vector<int>::iterator sit;			//集合元素迭代器
	cout << " 序号\t选中物品\t总重量\t总价值\t能否装入" << endl;
	for (it = ps.begin(); it != ps.end(); ++it) {
		cout << count + 1 << "\t";
		sumw = sumv = 0;
		cout << "{";
		for (sit = (*it).begin(); sit != (*it).end(); ++sit) {//将集合中元素对应的重量和价值相加
			cout << *sit << " ";
			sumw += w[*sit - 1];
			sumv += v[*sit - 1];
		}
		if((*it).size()>=3) cout<< "}\t" << sumw << "\t" << sumv << "\t";
		else cout << "}\t\t" << sumw << "\t" << sumv << "\t";
		if (sumw <= W) {			//判断能否放进背包
			cout << "能" << endl;
			if (sumv > maxv) {		//判断是否具有更大价值
				maxi = count;
				maxw = sumw;
				maxv = sumv;
			}
		}
		else cout << "否" << endl;
		++count;
	}
	cout << "最佳方案为:";
	cout << "选中物品{ ";
	for (sit = ps[maxi].begin(); sit != ps[maxi].end(); ++sit) {
		cout << *sit << " ";
	}
	cout << "},";
	cout << "总重量:" << maxw << ",总价值:" << maxv << endl;
}

int main() {
	int n = 4, W = 6;
	int w[] = { 5,3,2,1 };
	int v[] = { 4,4,3,1 };
	PSet(n);
	cout << "0/1背包求解方案" << endl;
	KNap(w, v, W);
	return 0;
}

总结:增量穷举法。

标签:ps,幂集,背包,求解,int,穷举法,vector,集合
From: https://www.cnblogs.com/QwertyWang/p/17788274.html

相关文章

  • 贪心法求解问题
    一、背包问题1.1问题描述  设有编号为1、2、......、n的n个物品,它们的重量分别为w1、w2、......、wn,价值分别为v1、v2、......、vn,其中wi和vi均为正数,有一个背包可以懈怠的最大重量不超过W。求解目标是在不超过背包附中的前提下使背包装入的总价值最大(即效益最大化)。与0/1背......
  • 浅谈动态规划——01背包
    本文暂时不谈记忆化搜索先看例题P1048采药(其实就是个加了题目背景的01背包板子题)我知道你可能不想读题,所以我把题意写在这里了题意你总共有T的时间有n个物品,第i个物品的价值为w[i],拿走它消耗的时间为v[i],且每个物品只能拿一次计算出能拿取的物品的最大总价值我猜你会这......
  • CSP20230917-3 梯度求解 题解
    〇、题目太长了懒得写。简单来说就是求对于一个后缀表达式,每个询问给出一个下标和一些值,求以该下标变量为自变量其它变量为常数时的偏导数。一、思路考虑直接对于表达式建出表达式树。建树的过程比较直接:每次栈里面放节点编号,遇到符号就取出当前栈顶两个节点作为子节点。每......
  • 利用中心极限定理求解圣彼得堡悖论问题的近似曲线
    此文为《概率论》课程小项目。关于圣彼得堡悖论的一些思考下面作模拟:importrandomimportmatplotlib.pyplotaspltMaxN=10000000defgetAward():award=1while(1):award*=2if(random.random()<=0.5):breakreturnawa......
  • 0-1背包问题
      ......
  • 递归求解N皇后问题
      ......
  • 非递归求解N皇后问题
      ......
  • 多重背包问题
    明天2023CSP了,简单写写,以后在补吧。题目描述P1833樱花给你若干个物品,每个物品有体积\(t_i\),价值\(c_i\),每个物品可以拿\(p_i\)次。特别的,当\(p_i=0\)的时候,这个物品可以取无数次。具体思路solution1:朴素背包对于\(p_i=0\)的物品,我们可以看成一个完全背包。......
  • 青蛙跳台阶(C语言数学排列组合公式求解法)
    题目:从前有一只青蛙他想跳台阶,有n级台阶,青蛙一次可以跳1级台阶,也可以跳2级台阶;问:该青蛙跳到第n级台阶一共有多少种跳法。当只有跳一级台阶的方法跳时,总共跳n步,共有1次跳法                 当用了一次跳二级台阶的方法跳时,总共跳n-1步,共有n-1次......
  • 01背包问题的子集树搜索
    如题: 经典01背包问题,直接代码反映心路历程。////Createdby_thinkPadon2023/10/16.//#include<iostream>#include<vector>#include<stack>#include<queue>#include<algorithm>usingnamespacestd;/**第一行两个整数,N,V,用空格隔开,分别表示物品数量和......