这两天看高程中的算法,把其中的递归背包问题用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;

}

}

}

以上代码复制、粘贴即可运行!

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; //??????

}

}