主定理，动态规划与分治，贪心算法，回溯
动态规划与分治：
动态规划与贪心：
分支界限法与回溯的分析：
贪心算法：https://blog.csdn.net/weixin_41413441/article/details/79195259
0-1背包问题 —— 四种解法解题：
https://www.cnblogs.com/xym4869/p/8513801.html
贪心算法之活动安排问题:
#include <iostream>
using namespace std;
void GreedSelector(int n,int s[],int f[],bool A[]);
const int n = 11;
int main()
{
int s[12]={0,1,3,0,5,3,5,6,8,8,2,12},f[12]={0,4,5,6,7,8,9,10,11,12,13,14};
bool A[n+1];
GreedSelector(n,s,f,A);
cout<<"最大相容活动安排为："<<endl;
for(int i=1;i<=n;i++)
{
if(A[i])
{
cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
}
}
return 0;
}
void GreedSelector(int n,int s[],int f[],bool A[])
{
A[1]=true;
int j=1;
for (int i=2;i<=n;i++)
{
if(s[i]>=f[j])
{
A[i]=true ;
j=i;
}
else
{
A[i]=false;
}
}
}
#include <stdio.h>
#include <stdlib.h>
typedef int bool;
#define true 1
#define false 0
int GreedSelector(int n,int s[],int f[],bool A[])
{
A[1]=true;
int i,j=1,count=1;
for (i=2;i<=n;i++)
{
if(s[i]>=f[j])
{
A[i]=true ;
j=i;
count++;
}
else A[i]=false;
}
return count;
}
int main()
{
int i,n=11;
int p;
int s[12]={0,1,3,0,5,3,5,6,8,8,2,12},f[12]={0,4,5,6,7,8,9,10,11,12,13,14};
bool A[12];
//printf("输入节目数：\n");
//scanf("%d",&n);
/*printf("请依次输入节目的开始和结束时间\n");
for(i=0;i<n;i++)
{
scanf("%d %d",&s[i],&f[i]);
}*/
p=GreedSelector(n,s,f,A);
printf("安排的节目个数为:%d\n",p);
printf("节目的选取情况为(0表示不选 1表示选取):\n");
for(i=1;i<=n;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}
动态规划法求解0/1背包问题：
#include <stdio.h>
#define N 100
#define MAX(a,b) a < b ? b : a
using namespace std;
struct goods{
int sign;//物品序号
int wight;//物品重量
int value;//物品价值
};
int n,bestValue,cv,cw,C;//物品数量，价值最大，当前价值，当前重量，背包容量
int X[N],cx[N];//最终存储状态，当前存储状态
struct goods goods[N];
int KnapSack(int n,struct goods a[],int C,int x[]){
int V[N][10*N];
for(int i = 0; i <= n; i++)//初始化第0列
V[i][0] = 0;
for(int j = 0; j <= C; j++)//初始化第0行
V[0][j] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= C; j++)
if(j < a[i-1].wight)
V[i][j] = V[i-1][j];
else
V[i][j] = MAX(V[i-1][j],V[i-1][j-a[i-1].wight] + a[i-1].value);
for(int i = n,j = C; i > 0; i--){
if(V[i][j] > V[i-1][j]){
x[i-1] = 1;
j = j - a[i-1].wight;
}
else
x[i-1] = 0;
}
return V[n][C];
}
int main()
{
printf("物品种类n：");
scanf("%d",&n);
printf("背包容量C：");
scanf("%d",&C);
for(int i = 0; i < n; i++){
printf("物品%d的重量w[%d]及其价值v[%d]：",i+1,i+1,i+1);
scanf("%d%d",&goods[i].wight,&goods[i].value);
}
int sum2 = KnapSack(n,goods,C,X);
printf("动态规划法求解0/1背包问题:\nX=[");
for(int i = 0; i < n; i++)
printf("%d",X[i]);
//cout<<X[i]<<" ";//输出所求X[n]矩阵
printf("] 装入总价值%d\n", sum2);
return 0;
}
回溯法求解0/1背包问题：
#include <iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100
struct goods{
int wight;//物品重量
int value;//物品价值
};
int n,bestValue,cv,cw,C;//物品数量，价值最大，当前价值，当前重量，背包容量
int X[N],cx[N];//最终存储状态，当前存储状态
struct goods goods[N];
int BackTrack(int i){
if(i > n-1){
if(bestValue < cv){
for(int k = 0; k < n; k++)
X[k] = cx[k];//存储最优路径
bestValue = cv;
}
return bestValue;
}
if(cw + goods[i].wight <= C){//进入左子树
cw += goods[i].wight;
cv += goods[i].value;
cx[i] = 1;//装入背包
BackTrack(i+1);
cw -= goods[i].wight;
cv -= goods[i].value;//回溯，进入右子树
}
cx[i] = 0;//不装入背包
BackTrack(i+1);
return bestValue;
}
bool m(struct goods a, struct goods b){
return (a.value/a.wight) > (b.value/b.wight);
}
int KnapSack3(int n, struct goods a[], int C,int x[N]){
memset(x,0,sizeof(x));
sort(a,a+n,m);//将各物品按单位重量价值降序排列
BackTrack(0);
return bestValue;
}
int main()
{
printf("物品种类n：");
scanf("%d",&n);
printf("背包容量C：");
scanf("%d",&C);
for(int i = 0; i < n; i++){
printf("物品%d的重量w[%d]及其价值v[%d]：",i+1,i+1,i+1);
scanf("%d%d",&goods[i].wight,&goods[i].value);
}
int sum3 = KnapSack3(n,goods,C,X);
printf("回溯法求解0/1背包问题:\nX=[");
for(int i = 0; i < n; i++)
cout << X[i] <<" ";//输出所求X[n]矩阵
printf("] 装入总价值%d\n",sum3);
return 0;
}
分支限界法求解背包问题 :
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100 //最多可能物体数
struct goods //物品结构体
{
int sign; //物品序号
int w; //物品重量
int p; //物品价值
}a[N];
bool m(goods a,goods b)
{
return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
return a<b?b:a;
}
int n,C,bestP=0,cp=0,cw=0;
int X[N],cx[N];
struct KNAPNODE //状态结构体
{
bool s1[N]; //当前放入物体
int k; //搜索深度
int b; //价值上界
int w; //物体重量
int p; //物体价值
};
struct HEAP //堆元素结构体
{
KNAPNODE *p;//结点数据
int b; //所指结点的上界
};
//交换两个堆元素
void swap(HEAP &a, HEAP&b)
{
HEAP temp = a;
a = b;
b = temp;
}
//堆中元素上移
void mov_up(HEAP H[], int i)
{
bool done = false;
if(i!=1){
while(!done && i!=1){
if(H[i].b>H[i/2].b){
swap(H[i], H[i/2]);
}else{
done = true;
}
i = i/2;
}
}
}
//堆中元素下移
void mov_down(HEAP H[], int n, int i)
{
bool done = false;
if((2*i)<=n){
while(!done && ((i = 2*i) <= n)){
if(i+1<=n && H[i+1].b > H[i].b){
i++;
}
if(H[i/2].b<H[i].b){
swap(H[i/2], H[i]);
}else{
done = true;
}
}
}
}
//往堆中插入结点
void insert(HEAP H[], HEAP x, int &n)
{
n++;
H[n] = x;
mov_up(H,n);
}
//删除堆中结点
void del(HEAP H[], int &n, int i)
{
HEAP x, y;
x = H[i]; y = H[n];
n --;
if(i<=n){
H[i] = y;
if(y.b>=x.b){
mov_up(H,i);
}else{
mov_down(H, n, i);
}
}
}
//获得堆顶元素并删除
HEAP del_top(HEAP H[], int&n)
{
HEAP x = H[1];
del(H, n, 1);
return x;
}
//计算分支节点的上界
void bound( KNAPNODE* node,int M, goods a[], int n)
{
int i = node->k;
float w = node->w;
float p = node->p;
if(node->w>M){ // 物体重量超过背包载重量
node->b = 0; // 上界置为0
}else{
while((w+a[i].w<=M)&&(i<n)){
w += a[i].w; // 计算背包已装入载重
p += a[i++].p; // 计算背包已装入价值
}
if(i<n){
node->b = p + (M - w)*a[i].p/a[i].w;
}else{
node -> b = p;
}
}
}
//用分支限界法实现0/1背包问题
int KnapSack4(int n,goodsa[],int C, int X[])
{
int i, k = 0; // 堆中元素个数的计数器初始化为0
int v;
KNAPNODE *xnode, *ynode, *znode;
HEAP x, y, z, *heap;
heap = new HEAP[n*n]; // 分配堆的存储空间
for( i=0; i<n; i++){
a[i].sign=i; //记录物体的初始编号
}
sort(a,a+n,m); // 对物体按照价值重量比排序
xnode = new KNAPNODE; // 建立父亲结点
for( i=0; i<n; i++){ // 初始化结点
xnode->s1[i] = false;
}
xnode->k = xnode->w = xnode->p = 0;
while(xnode->k<n) {
ynode = new KNAPNODE; // 建立结点y
*ynode = *xnode; //结点x的数据复制到结点y
ynode->s1[ynode->k] = true; // 装入第k个物体
ynode->w += a[ynode->k].w; // 背包中物体重量累计
ynode->p += a[ynode->k].p; // 背包中物体价值累计
ynode->k ++; // 搜索深度++
bound(ynode, C, a, n); // 计算结点y的上界
y.b = ynode->b;
y.p = ynode;
insert(heap, y, k); //结点y按上界的值插入堆中
znode = new KNAPNODE; // 建立结点z
*znode = *xnode; //结点x的数据复制到结点z
znode->k++; // 搜索深度++
bound(znode, C, a, n); //计算节点z的上界
z.b = znode->b;
z.p = znode;
insert(heap, z, k); //结点z按上界的值插入堆中
delete xnode;
x = del_top(heap, k); //获得堆顶元素作为新的父亲结点
xnode = x.p;
}
v = xnode->p;
for( i=0; i<n; i++){ //取装入背包中物体在排序前的序号
if(xnode->s1[i]){
X[a[i].sign] =1 ;
}else{
X[a[i].sign] = 0;
}
}
delete xnode;
delete heap;
return v; //返回背包中物体的价值
}
/*测试以上算法的主函数*/
int main()
{
goods b[N];
printf("物品种数n: ");
scanf("%d",&n); //输入物品种数
printf("背包容量C: ");
scanf("%d",&C); //输入背包容量
for (int i=0;i<n;i++) //输入物品i的重量w及其价值v
{
printf("物品%d的重量w[%d]及其价值v[%d]: ",i+1,i+1,i+1);
scanf("%d%d",&a[i].w,&a[i].p);
b[i]=a[i];
}
int sum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题
printf("分支限界法求解0/1背包问题:\nX=[ ");
for(i=0;i<n;i++)
cout<<X[i]<<" ";//输出所求X[n]矩阵
printf("] 装入总价值%d\n",sum4);
return 0;
}