/*贪心算法求得的是局部最优解，而不是整体最优解
*归纳起来就是先求出每个物品的平均价值（也就是价值/重量）;
*然后再将得出来的每个物品的平均价值降序排序，并记录各自在数组中的位置（即下标）
*将排序后的物品重量和价值分别用新数组来存储
*根据背包容量来判断，一件一件装入背包，直到装满为止，在这个过程中通过解向量判断是否已经装满
*最后根据解向量算出装入物品的价值
*/
package test;
import java.util.Arrays;
import java.util.Scanner;
//
public class Greedy {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.println("Please enter the number of objects(请输入物品的数量：)");
int n = in.nextInt();
int[] w = new int[n]; //物品重量数组weight
int[] v = new int[n]; //物品价值数组value
System.out.println("Now please enter the weight of the objects(现在请输入这些物品的重量：)");
for(int i=0;i
w[i] = in.nextInt();
}
System.out.println("Now please enter the value of the ojects(现在请输入这些物品的价值：)");
for(int j=0;j
v[j] = in.nextInt();
}
System.out.println("Now please enter the capacity of the pack(请输入背包的容积：)");
int c = in.nextInt();
double startTime = System.currentTimeMillis();
int[] index = new int[n];
double[] r = new double[n]; //定义物品的质量价值
for(int k=0;k
r[k] = v[k]/w[k]; //获取物品的重量价值
index[k] = k;
}
//采用选择排序的方法来求解
double temp = 0;
int x = 0;
for(int i=0;i
for(int j=i+1;j
if(r[i]
temp = r[i];
r[i] = r[j];
r[j] = temp;
x = index[i];
index[i] = index[j];
index[j] = x;
}
}
}
//将排序后的重量和价值存放在新的数组中
int[] w1 = new int[n];
int[] v1 = new int[n];
for(int i=0;i
v1[i] = v[index[i]];
w1[i] = w[index[i]];
}
//初始化解向量
int[] x1 = new int[n];
for (int i = 0; i
x1[i] = 0;
}
/*
* 求解并打印向量
*/
for(int i=0;i
if(w1[i]
x1[i] = 1;
c = c-w1[i];
}
}
System.out.println("The solution vector is(解向量是：)"+Arrays.toString(x1));
/*
* 根据解向量求出最大价值并打印出来
*/
int maxValue=0;
for(int i=0;i
if(x1[i]==1){
maxValue = maxValue+v1[i];
}
}
System.out.println("Now,the max value of object in the pack is(背包可以容纳的最大价值是：)"+maxValue);
//算法结束时间
double endTime = System.currentTimeMillis();
System.out.println("The Statements takes the time is(算法执行所花费的时间为：)"+(endTi
me-startTime)+ " milliseconds!");
}
}
/*贪心算法求得的是局部最优解，而不是整体最优解
*归纳起来就是先求出每个物品的平均价值（也就是价值/重量）;
*然后再将得出来的每个物品的平均价值降序排序，并记录各自在数组中的位置（即下标）
*将排序后的物品重量和价值分别用新数组来存储
*根据背包容量来判断，一件一件装入背包，直到装满为止，在这个过程中通过解向量判断是否已经装满
*最后根据解向量算出装入物品的价值
*/
package test;
import java.util.Arrays;
import java.util.Scanner;
//
public class Greedy {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
System.out.println("Please enter the number of objects(请输入物品的数量：)");
int n = in.nextInt();
int[] w = new int[n]; //物品重量数组weight
int[] v = new int[n]; //物品价值数组value
System.out.println("Now please enter the weight of the objects(现在请输入这些物品的重量：)");
for(int i=0;i
w[i] = in.nextInt();
}
System.out.println("Now please enter the value of the ojects(现在请输入这些物品的价值：)");
for(int j=0;j
v[j] = in.nextInt();
}
System.out.println("Now please enter the capacity of the pack(请输入背包的容积：)");
int c = in.nextInt();
double startTime = System.currentTimeMillis();
int[] index = new int[n];
double[] r = new double[n]; //定义物品的质量价值
for(int k=0;k
r[k] = v[k]/w[k]; //获取物品的重量价值
index[k] = k;
}
//采用选择排序的方法来求解
double temp = 0;
int x = 0;
for(int i=0;i
for(int j=i+1;j
if(r[i]
temp = r[i];
r[i] = r[j];
r[j] = temp;
x = index[i];
index[i] = index[j];
index[j] = x;
}
}
}
//将排序后的重量和价值存放在新的数组中
int[] w1 = new int[n];
int[] v1 = new int[n];
for(int i=0;i
v1[i] = v[index[i]];
w1[i] = w[index[i]];
}
//初始化解向量
int[] x1 = new int[n];
for (int i = 0; i
x1[i] = 0;
}
/*
* 求解并打印向量
*/
for(int i=0;i
if(w1[i]
x1[i] = 1;
c = c-w1[i];
}
}
System.out.println("The solution vector is(解向量是：)"+Arrays.toString(x1));
/*
* 根据解向量求出最大价值并打印出来
*/
int maxValue=0;
for(int i=0;i
if(x1[i]==1){
maxValue = maxValue+v1[i];
}
}
System.out.println("Now,the max value of object in the pack is(背包可以容纳的最大价值是：)"+maxValue);
//算法结束时间
double endTime = System.currentTimeMillis();
System.out.println("The Statements takes the time is(算法执行所花费的时间为：)"+(endTi
me-startTime)+ " milliseconds!");
}
}