0-1背包回溯法java实现
5星 · 超过95%的资源 需积分: 31 161 浏览量
2013-01-01
19:18:33
上传
评论 1
收藏 33KB DOC 举报 
/*
* 0-1背包问题--采用回溯法解决--回溯法中的子集树
* Time：2012-1-1
* 下标从1开始
*/
package com.book.java;
public class Project39_Knapsack {
public static int c=7;//用来表示最大的容量
public static int weight[]={0,3,5,2,1};//用来表示各个物品的质量，从下标1
开始
public static int value[]={0,9,10,7,4};//用来表示各个物品的价值，从下标1
开始
// public static int c=10;
// public static int []weight={0,2,2,6,5,4};
// public static int []value ={0,6,3,5,4,6};
public static int n;//用来存储数组的个数
public static int cur; //用来存储当前的质量
public static int curv;//当前的价值
public static int bestv;//最佳的价值
public static int x[];//用来存储最佳的物品选择
public static int curx[];//用来存储当前的物品选择
public static int remain;//用来存储选择后的剩余的存储，用于在减去分支使用
public static void main(String[] args) {
//初始化各个变量
n=weight.length-1;
cur=0;
curv=0;
bestv=0;
x=new int[n+1];
curx=new int[n+1];
for(int i=1;i<=n;i++)
{
remain+=value[i];//remain初始的时候，初始化为所有的价值之和
}
traceback(1);//调用装包的方式
//输出结果
System.out.println("最佳的装包的价值为:"+bestv);
System.out.println("装包的方式为:");
for(int i=1;i<=n;i++)
{
System.out.print(x[i]+" ");
}
}
public static void traceback(int num)
{
if(num>n) //搜索到最后的时候，进行判断此时的方式是否为最佳的装包方式
{
// System.out.println("到达n的时候:");
// System.out.println("当前价值为："+curv);
- 1
- 2
前往页