运用贪心策略解决0 1背包问题
void beibao(int *w,int *v,int *x,int n,int *C)
{
int i,j,temp;
for(i=0;in;
w=new int(n);//动态分配内存
v=new int(n);
x=new int(n);
cout<<"请输入背包的容量"<>C;
cout<<"请分别输入"<w[i];
cout<<"请分别输入"<v[i];
beibao(w,v,x,n,&C);
cout<<"应用贪心策略装入背包的物品的重量分别为:"<
2019-12-21 21:35:05
901B
1
使用蚁群算法实现了单维的01背包问题，自己写的，可直接运行AcoKP.java文件即可输出结果，收敛速度还可以，可根据自己需要修改参数
2019-12-21 21:25:53
4KB
1
经典遗传算法(SGA)解01背包问题的python代码实现，说明如下：
1.采用经典的二进制编码，选择算子为轮盘赌选择，交叉算子为两点交叉，变异算子为反转（单点）变异
2.可调的参数为：gen,pc,pm,popsize,n,w,c,W,M
3.两种解码方式：带惩罚项和不带惩罚项
2019-12-21 20:52:25
5KB
1
01背包问题属于组合优化问题的一个例子，求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：
给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。
2019-12-21 20:37:52
16KB
1
基于matlab的01背包源码实现，纯手写，仅供新手学习和参考...由于代码比较简单，所以没有过多的注释，大家可以根据网上的帖子理解01背包的动态规划思想，再自己临摹代码进行学习
2019-12-21 20:37:42
1KB
1
买书问题 dp实现
题目：买书
有一书店引进了一套书，共有3卷，每卷书定价是60元，书店为了搞促销，推出一个活动，活动如下：
如果单独购买其中一卷，那么可以打9.5折。
如果同时购买两卷不同的，那么可以打9折。
如果同时购买三卷不同的，那么可以打8.5折。
如果小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少需要多少钱呢？（x、y、z为三个已知整数）。
1、过程为一次一次的购买，每一次购买也许只买一本（这有三种方案），或者买两本（这也有三种方案），
或者三本一起买（这有一种方案），最后直到买完所有需要的书。
2、最后一步我必然会在7种购买方案中选择一种，因此我要在7种购买方案中选择一个最佳情况。
3、子问题是，我选择了某个方案后，如何使得购买剩余的书能用最少的钱？并且这个选择不会使得剩余的书为负数
。母问题和子问题都是给定三卷书的购买量，求最少需要用的钱，所以有"子问题重叠"，问题中三个购买量设置为参数，
分别为i、j、k。
4、的确符合。
5、边界是一次购买就可以买完所有的书，处理方式请读者自己考虑。
6、每次选择最多有7种方案，并且不会同时实施其中多种，因此方案的选择互不影响，所以有"子问题独立"。
7、我可以用minMoney[i][j][k]来保存购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱。
8、共有x * y * z个问题，每个问题面对7种选择，时间为：O( x * y * z * 7) = O( x * y* z )。
9、用函数MinMoney(i,j,k)来表示购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱，那么有：
MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分别为对应的7种方案使用的最少金钱：
s1 = 60 * 0.95 + MinMoney(i-1,j,k)
s2 = 60 * 0.95 + MinMoney(i,j-1,k)
s3 = 60 * 0.95 + MinMoney(i,j,k-1)
s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)
s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)
2019-12-21 20:31:08
3KB
1