一、幂集问题
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