package qinglin.learn.arithmetic;
public class SackPro_02
{
int p[] =new int[]{9,10,7,4};
int w[] =new int[]{3,5,2,1};
int cp[]=new int[p.length];
int cw[]=new int[w.length];
int x[]=new int[p.length];
int cx[]=new int[p.length];
int currentP,currentW,bestp;
private void printResult()
{
System.out.println("可以装入的最大价值为:"+bestp);
System.out.println("装入的物品依次为:");
for(int i = 0; i < x.length; i++)
{
if(x[i]==1)
System.out.print((i+1)+" ");
}
}
void backtrack(int i)
{
if(i >= 4)
{
if(currentP > bestp)
{
bestp = currentP;
for(int j = 0; j < 4; j++)
x[j] = cx[j];
}
return;
}
if(currentW + w[i] <= 7)
{//搜索右子树
currentW += w[i];
currentP += p[i];
cx[i] = 1;
backtrack(i+1);
currentW -= w[i];
currentP -= p[i];
cx[i] = 0;
}
backtrack(i+1);//搜索左子树
}
public static void main(String[] args)
{
SackPro_02 example = new SackPro_02();
example.backtrack(0);
example.printResult();
}
}
分享到:
相关推荐
算法效果较为良好,实现背包问题价值最大,采用遗传算法实现的比较不错的结果
通过遗传算法实现背包问题最优解求解,包括代码文档。
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
完全背包问题N件物品放入容量为C的背包。第i件物品的费用(重量、体积等)为wi,价值为vi。每件物品可以取用任意多次(无限数量),选择将哪些物品放入背包令总费用不超过背包的容量且物品的价值总和最大。输入格式...
课程作业,实现算法实践书后的例题,实现01背包问题
Matlab 代码,用遗传算法解决01背包问题
计算机算法分析第四章,背包问题最优装载问题证明等的以及讲义
用遗传算法解决背包问题,供大家参考交流。。。
这是背包问题的程序,用matlab实现,背包问题是NP完全问题
利用MATLAB,解决0-1背包问题,数据带入已经包含在主程序段里。需要使用直接粘贴到MATLAB更改数据即可
0-1背包问题问题,使用的回溯算法来实现了。挺简单的实现。
动态规划算法 0-1背包问题 各种各样的背包问题的原理分析
这是最基础的背包问题
基于粒子群优化算法的0-1背包问题,能正常运行,效果很好。
背包问题(Knapsack problem)是一种组合优化的NP完全问题
模拟退火算法解决0-1背包问题,检测结果真实有效
0-1背包问题_算法设计C++ 可以实现 大家分享学习
粒子群背包问题,最多处理数据500条.输入 pso 回车即可
模拟退火算法求解0-1背包问题。模拟退火算法求解0-1背包问题
背包问题0,1问题,贪婪算法MATLAB源程序