#include <stdio.h>
#define N 7
int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30}
char name[] = "ABCDEFG"
int max = 0, Max[N] /*max用于存放最大价值，Max用于存放最优解向量*/
int v[N]/*v：求解时用于存放求解过程向量*/
template <class T>
void Swap(T &a, T &b)
{
T tmp = a
a = b, b = tmp
}
void Knapsack(int step, int bag, int value1, int value2, int n)
/*step表示第step步的选择（即第step个物品的选择），bag为背包剩余容量，value1表示包中现有物品总价值，value2表示剩余物品总价值，n为物品总数量*/
{
int i
if((step >= n) || (weight[step] >bag) || (value1 + value2 <= max)) /*如果所有物品都选择完毕或剩余的物品都放不进或者包中物品总价值与剩余物品总价值之和小于等于目前的已知解，则找到一个解(但不一定是最终解或更优解)*/
{
for(i = stepi <ni++) v[i] = 0 /*剩余的物品都不放入*/
if(value1 >max) /*如果本次求得的解比以往的解更优，则将本次解作为更优解*/
{
max = value1
for(i = 0i <ni++) Max[i] = v[i] /*将更优解保存到Max向量中*/
}
return
}
v[step] = 0, Knapsack(step + 1, bag, value1, value2 - cost[step], n) /*不将第step个物品放入背包，第step个物品的价值被放弃，进行下一步的选择*/
v[step] = 1, Knapsack(step + 1, bag - weight[step], value1 + cost[step], value2 - cost[step], n)/*将第step个物品放入背包，进行下一步的选择*/
}
void main( )
{
/*输入数据：背包容量、物品数量、重量、价值 代码略*/
int bag = 150, i, j, min, totalcost
/*按物品重量从小到大的顺序对物品排序，排序时cost向量中的相对顺序也要作相应移动*/
for(i = 0i <N - 1i++) {
for(min = i, j = i + 1j <Nj++)
if(weight[j] <weight[min]) min = j
if(i != min) {
Swap(weight[i], weight[min])
Swap(cost[i], cost[min])
Swap(name[i], name[min])
}
}
for(totalcost = 0, i = 0i <Ni++) totalcost += cost[i] /*求总价值*/
Knapsack(0, bag, 0, totalcost, N)/*bag为空背包容量, totalcost为物品总价值, N为物品数量*/
/*以下输出解*/
printf("最大价值为: %d。\n装入背包的物品依次为：\n", max)
for(i = 0i <Ni++)
if(Max[i]) printf("%c\t", name[i])
printf("\n")
}
我的回答你满意吗？如果满意，就请采纳哦，或者你也可以继续追问。
/*给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
*/
#include <iostream>
using namespace std
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define ERROR -1
typedef float value
typedef float weight
typedef int KeyType// 定义关键字类型为整数类型
typedef struct //元素定义
{
weight w//重量
value v//价值
value q//单位重量价值
int index//序号
bool job//表示是否被用
}Bag
typedef struct //定义背包集
{
Bag r[MAXSIZE+1]//r[0]闲置或用作 “ 哨兵单元”
int length//背包个数
}Bags
int n//包个数
int i//辅助整型变量
weight c//背包的容量
weight cw//当前重量
value bestp=0//当前最优价值
value cp//当前价值
Bags L//定义背包集
int Partition(Bags &L,int low,int high) //快速排序
// 交换顺序表L中子表r[low.....high]的记录,枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它.
{
int shuzhou//定义枢轴
L.r[0]=L.r[low]//用第一个记录作为枢轴记录
shuzhou=L.r[low].q
while(low<high)
{
while(low<high &&L.r[high].q>=shuzhou)
--high
L.r[low]=L.r[high]
while(low<high &&L.r[low].q<=shuzhou)
++low
L.r[high]=L.r[low]
}
L.r[low]=L.r[0]
return low
}//Partition
void QuickSort(Bags &L,int low,int high) //快速排序
//对顺序表L[low ....high]作快速排序
{
int shuzhou
if(low<high)
{
shuzhou=Partition(L,low,high)// 获得枢轴
QuickSort(L,low,(shuzhou-1))//对枢轴前半部分排序
QuickSort(L,(shuzhou+1),high)//对枢轴后半部分排序
}
}//QuickSort
value bound(int i)
{//计算上界
weight left=c-cw//剩余容量
value bound=cp
//以物品单位重量价值递减顺序装入物品
while(i<=n&&L.r[i].w<=left)
{
left-=L.r[i].w
bound+=L.r[i].v
i++
}
//装满背包
if(i<=n)
bound+=L.r[i].v*left/L.r[i].w
return bound
}//bound
void backtrack(int i)
{
if(i>n)
{//到达叶子结点
bestp=cp
return
}
//搜索子树
if(cw+L.r[i].w<=c)
{//进入左子树
cw+=L.r[i].w
cp+=L.r[i].v
//L.r[i].job=true//选中
backtrack(i+1)
cw-=L.r[i].w
cp-=L.r[i].v
//L.r[i].job=false//未选中
}
if(bound(i+1)>bestp)//进入右子树
backtrack(i+1)
}//backtrack
void knapsack(weight c)//0-1背包问题主算法
{
QuickSort(L,1,L.length)
backtrack(1)//回溯搜索
}//knapsack
int main()
{
//输入要选择的背包信息
cout<<"请输入背包的容量:"
cin>>c
cout<<"请输入物品个数（注意：不能超过 100个!）:"
cin>>n
if(n>100)
{
cout<<"你输入的物品个数太多!!!"<<endl
return FALSE
}
L.length=n
for(i=1i<=ni++)
{
cout<<"请输入第个"<<i<<"物品的重量："
cin>>L.r[i].w
cout<<"请输入第个"<<i<<"物品的价值："
cin>>L.r[i].v
L.r[i].q=L.r[i].v/L.r[i].w//单位重量价值
L.r[i].index=i//索引号
cout<<endl
}
//执行0-1背包问题主算法
knapsack(c)
//输出结果
for(i=1i<=ni++)
if(L.r[i].job)
cout<<"第个"<<L.r[i].index<<"物品被选中"<<endl
cout<<"被选中的物品的总价值为： "<<bestp<<endl
return TRUE
}
/*
template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i)
{// 计算上界
Typew cleft = c - cw// 剩余容量
Typep b = cp
// 以物品单位重量价值递减序装入物品
while (i <= n &&w[i] <= cleft) {
cleft -= w[i]
b += p[i]
i++
}
// 装满背包
if (i <= n) b += p[i]/w[i] * cleft
return b
}
*/
#include<iostream>using namespace std
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n )
public:
//输出当前最优解
void print()
{
for(int m=1m<=nm++)
{
cout<<bestx[m]<<" "
}
cout<<endl
}
private:
int Bound(int i)//计算右子树的上界
void Backtrack(int i)
int c//背包容量
int n//物品数
int *w//物品重量数组
int *p//物品价值数组
int cw//当前重量
int cp//当前价值
int bestp//当前最优值
int *bestx//当前最优解
int *x//当前解
}
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw//剩余容量
int b=cp
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i]
b+=p[i]
i++
}
//剩余物品取部分来装满背包
if(i<=n)
b+=p[i]/w[i]*cleft
return b
}
void Knap::Backtrack(int i)
{
if(i>n)//到达叶结点
{
if(bestp<cp)
{
for(int j=1j<=nj++)
bestx[j]=x[j]//更新当前最优解
bestp=cp
}
return
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1//装入
cw+=w[i]
cp+=p[i]
Backtrack(i+1)
cw-=w[i]
cp-=p[i]
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0//不装入
Backtrack(i+1)
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n)
public:
int operator<=(Object a)const
{
return (d>=a.d)
}
private:
int ID
float d//单位重量价值
}
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0
int P=0
int i=1
Object *Q=new Object[n]
for(i=1i<=ni++)
{
Q[i-1].ID=i
Q[i-1].d=1.0*p[i]/w[i]//计算单位重量价值
P+=p[i]
W+=w[i]
}
if(W<=c)
return P//装入所有物品
//依物品单位重量排序
float f
for( i=0i<ni++)
for(int j=ij<nj++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d
Q[i].d=Q[j].d
Q[j].d=f
}
}
Knap K
K.p = new int[n+1]
K.w = new int[n+1]
K.x = new int[n+1]
K.bestx = new int[n+1]
K.x[0]=0
K.bestx[0]=0
for( i=1i<=ni++)
{
K.p[i]=p[Q[i-1].ID]
K.w[i]=w[Q[i-1].ID]
}
K.cp=0
K.cw=0
K.c=c
K.n=n
K.bestp=0
//回溯搜索
K.Backtrack(1)
K.print()
delete [] Q
delete [] K.w
delete [] K.p
return K.bestp
}
void main()
{
int *p
int *w
int c=7
int n=4
int i=0
p=new int[n+1]
w=new int[n+1]
p[0]=0
w[0]=0
p[1]=9w[1]=3
p[2]=10w[2]=5
p[3]=7w[3]=2
p[4]=4w[4]=1
cout<<Knapsack(p,w,c,n)<<endl
system("pause")
}
