这两天看高程中的算法，把其中的递归背包问题用java运行了。特请高手们指点！
05-04-04
seemee
/*
* Created on Apr 2, 2005
*
* To change the template for this generated file go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
package com.kevin.datastru;
/**
* @author seemee
*
* To change the template for this generated type comment go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
/*import java.io.BufferedReader;
import java.io.InputStreamReader;*/
import java.io.IOException;
public class CarryBag {
double limitW, totV, maxv;
int option[] = new int[100], cop[] = new int[100];
Struct a[]= new Struct[100];
int n;
public void find(int i, double tw, double tv){
int k;
if ( tw + a.weight <= limitW){
cop=1;
if(i<n-1){
find(i+1, tw+a.weight, tv);
}
else {
for(k=0;k<n;k++){
option[k] = cop[k];
}
maxv = tv;
}
cop = 0;
}
if (tv - a.value > maxv) {
if (i < n-1) {
find(i+1, tw, tv - a.value);
}
else {
for (k = 0; k<n; k++){
option[k] = cop[k];
}
maxv = tv - a.value;
}
}
}
public static void main(String[] args) throws IOException{
int k;
CarryBag cBag = new CarryBag();
cBag.a[0] = cBag.new Struct(5.0, 4.0);
cBag.a[1] = cBag.new Struct (3.0, 4.0);
cBag.a[2] = cBag.new Struct (2.0, 3.0);
cBag.a[3] = cBag.new Struct (1.0, 1.0);
cBag.limitW = 7.0;
cBag.maxv = 0.0;
cBag.totV = 12.0;
cBag.n = 4;
for (k = 0; k < cBag.n ; k++) {
cBag.cop[k] = 0;
}
cBag.find(0, 0.0, cBag.totV);
for(k = 0; k < cBag.n ; k++){
if(cBag.option[k] != 0) {
System.out.println(k);
}
}
System.out.println(cBag.maxv);
}
class Struct{
double weight;
double value;
Struct (double weight, double value){
this.weight = weight;
this.value = value;
}
}
}
以上代码复制、粘贴即可运行！
* Created on Apr 2, 2005
*
* To change the template for this generated file go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
package com.kevin.datastru;
/**
* @author seemee
*
* To change the template for this generated type comment go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
/*import java.io.BufferedReader;
import java.io.InputStreamReader;*/
import java.io.IOException;
public class CarryBag {
double limitW, totV, maxv;
int option[] = new int[100], cop[] = new int[100];
Struct a[]= new Struct[100];
int n;
public void find(int i, double tw, double tv){
int k;
if ( tw + a.weight <= limitW){
cop=1;
if(i<n-1){
find(i+1, tw+a.weight, tv);
}
else {
for(k=0;k<n;k++){
option[k] = cop[k];
}
maxv = tv;
}
cop = 0;
}
if (tv - a.value > maxv) {
if (i < n-1) {
find(i+1, tw, tv - a.value);
}
else {
for (k = 0; k<n; k++){
option[k] = cop[k];
}
maxv = tv - a.value;
}
}
}
public static void main(String[] args) throws IOException{
int k;
CarryBag cBag = new CarryBag();
cBag.a[0] = cBag.new Struct(5.0, 4.0);
cBag.a[1] = cBag.new Struct (3.0, 4.0);
cBag.a[2] = cBag.new Struct (2.0, 3.0);
cBag.a[3] = cBag.new Struct (1.0, 1.0);
cBag.limitW = 7.0;
cBag.maxv = 0.0;
cBag.totV = 12.0;
cBag.n = 4;
for (k = 0; k < cBag.n ; k++) {
cBag.cop[k] = 0;
}
cBag.find(0, 0.0, cBag.totV);
for(k = 0; k < cBag.n ; k++){
if(cBag.option[k] != 0) {
System.out.println(k);
}
}
System.out.println(cBag.maxv);
}
class Struct{
double weight;
double value;
Struct (double weight, double value){
this.weight = weight;
this.value = value;
}
}
}
以上代码复制、粘贴即可运行！
seemee
2005-04-04 10:51
尤其是用递推实现，我花了较长时间才隐隐约约理解。
在eclipse中写的，中文注释变成乱码了。大家可以讨论讨论！
/*
* Created on Apr 3, 2005
*
* To change the template for this generated file go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
package com.kevin.datastru;
/**
* senior programmer P4
* @author seemee
*
* To change the template for this generated type comment go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
public class CarryBag2 {
double limitW, maxv;
int cop[] = new int[10];
TwvClass twv[] = new TwvClass[10];
Struct a[]= new Struct[10];
int n; //????
/**
* ???i???
* @param i
* @param tw ???????
* @param tv ??????
*/
public void next(int i, double tw, double tv){
twv.flag = 1; /*???????*/
twv.tw = tw;
twv.tv = tv;
}
public double find(Struct a[], int n){
int i,k,f;
double maxv, tw, tv, totv;
maxv = 0; //??????0
//?????totv
for(totv = 0.0, k=0; k < n; k++){
totv += a[k].value;
}
next(0, 0.0, totv); //??????????????????find(0,0.0,totV)??
i = 0;
while(i >= 0){
f = twv.flag;
tw = twv.tw;
tv = twv.tv;
switch(f){
case 1:
twv.flag++; //???"???"?flag = 2
if(tw + a.weight <= limitW){ //??????
if(i < n-1){ //????????
next(i+1, tw+a.weight, tv); //?i+1?????
i++;
}
else { //?????????
maxv = tv;
for(k=0; k<n; k++){
cop[k] = twv[k].flag;
}
}
}
break;
case 0: //??
i--;
break;
default: // ??f == 2
twv.flag = 0; //??????
if(tv - a.value >maxv){ //??i???????
if(i < n - 1){ //????????
next(i+1, tw, tv-a.value);
i++;
}
else{
maxv = tv- a.value;
for (k = 0; k < n; k++){
cop[k] = twv[k].flag;
}
}
}
break;
} //end switch
}
return maxv;
}
public static void main(String[] args) {
/*-- ?????? ---*/
CarryBag2 cBag = new CarryBag2();
/*??????*/
cBag.a[0] = cBag.new Struct(5.0, 4.0);
cBag.a[1] = cBag.new Struct (3.0, 4.0);
cBag.a[2] = cBag.new Struct (2.0, 3.0);
cBag.a[3] = cBag.new Struct (1.0, 1.0);
/*?????TwvClass?????twv[]??*/
cBag.twv[0] = cBag.new TwvClass();
cBag.twv[1] = cBag.new TwvClass();
cBag.twv[2] = cBag.new TwvClass();
cBag.twv[3] = cBag.new TwvClass();
cBag.twv[4] = cBag.new TwvClass();
cBag.limitW = 7.0; //????
cBag.n = 4; //????
cBag.maxv = cBag.find(cBag.a, cBag.n); //?????
for(int k = 0; k < cBag.n ; k++){
if(cBag.cop[k] != 0) {
System.out.println(k);
}
}
System.out.println(cBag.maxv);
}
/**
* ???????
* @author seemee
*
*/
class Struct{
double weight; //?????
double value; //?????
Struct (double weight, double value){
this.weight = weight;
this.value = value;
}
}
/**
* ??????????????????????????????
* @author seemee
*
*/
class TwvClass{
int flag; //????????0?????????2?????
double tw; //???????
double tv; //??????
}
}
在eclipse中写的，中文注释变成乱码了。大家可以讨论讨论！
/*
* Created on Apr 3, 2005
*
* To change the template for this generated file go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
package com.kevin.datastru;
/**
* senior programmer P4
* @author seemee
*
* To change the template for this generated type comment go to
* Window - Preferences - Java - Code Generation - Code and Comments
*/
public class CarryBag2 {
double limitW, maxv;
int cop[] = new int[10];
TwvClass twv[] = new TwvClass[10];
Struct a[]= new Struct[10];
int n; //????
/**
* ???i???
* @param i
* @param tw ???????
* @param tv ??????
*/
public void next(int i, double tw, double tv){
twv.flag = 1; /*???????*/
twv.tw = tw;
twv.tv = tv;
}
public double find(Struct a[], int n){
int i,k,f;
double maxv, tw, tv, totv;
maxv = 0; //??????0
//?????totv
for(totv = 0.0, k=0; k < n; k++){
totv += a[k].value;
}
next(0, 0.0, totv); //??????????????????find(0,0.0,totV)??
i = 0;
while(i >= 0){
f = twv.flag;
tw = twv.tw;
tv = twv.tv;
switch(f){
case 1:
twv.flag++; //???"???"?flag = 2
if(tw + a.weight <= limitW){ //??????
if(i < n-1){ //????????
next(i+1, tw+a.weight, tv); //?i+1?????
i++;
}
else { //?????????
maxv = tv;
for(k=0; k<n; k++){
cop[k] = twv[k].flag;
}
}
}
break;
case 0: //??
i--;
break;
default: // ??f == 2
twv.flag = 0; //??????
if(tv - a.value >maxv){ //??i???????
if(i < n - 1){ //????????
next(i+1, tw, tv-a.value);
i++;
}
else{
maxv = tv- a.value;
for (k = 0; k < n; k++){
cop[k] = twv[k].flag;
}
}
}
break;
} //end switch
}
return maxv;
}
public static void main(String[] args) {
/*-- ?????? ---*/
CarryBag2 cBag = new CarryBag2();
/*??????*/
cBag.a[0] = cBag.new Struct(5.0, 4.0);
cBag.a[1] = cBag.new Struct (3.0, 4.0);
cBag.a[2] = cBag.new Struct (2.0, 3.0);
cBag.a[3] = cBag.new Struct (1.0, 1.0);
/*?????TwvClass?????twv[]??*/
cBag.twv[0] = cBag.new TwvClass();
cBag.twv[1] = cBag.new TwvClass();
cBag.twv[2] = cBag.new TwvClass();
cBag.twv[3] = cBag.new TwvClass();
cBag.twv[4] = cBag.new TwvClass();
cBag.limitW = 7.0; //????
cBag.n = 4; //????
cBag.maxv = cBag.find(cBag.a, cBag.n); //?????
for(int k = 0; k < cBag.n ; k++){
if(cBag.cop[k] != 0) {
System.out.println(k);
}
}
System.out.println(cBag.maxv);
}
/**
* ???????
* @author seemee
*
*/
class Struct{
double weight; //?????
double value; //?????
Struct (double weight, double value){
this.weight = weight;
this.value = value;
}
}
/**
* ??????????????????????????????
* @author seemee
*
*/
class TwvClass{
int flag; //????????0?????????2?????
double tw; //???????
double tv; //??????
}
}