背包問(wèn)題
有一個(gè)背包，背包容量是M=150嫁乘。有7個(gè)物品蹦浦，物品可以分割成任意大小扭吁。
要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?br>
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價(jià)值 10 40 30 50 35 40 30
貪心算法描述：
1.改變數(shù)組w和v的排列順序盲镶，使其按單位重量?jī)r(jià)值v[i]/w[i]降序排列侥袜；
2.將數(shù)組x[n]初始化為0； //初始化向量
- i=1;
4.循環(huán)直到（w[i]>C);
4.1 x[i]=1;
4.2 C=C-w[i];
4.3 i++; - x[i]=C/w[i]; **/
public class Package2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("請(qǐng)輸入物品的數(shù)量:");
int n = in.nextInt();
int[] w = new int[n];
int[] v = new int[n];
System.out.println("現(xiàn)在請(qǐng)輸入這些物品的重量:");
for (int i = 0; i < n; i++) {
w[i] = in.nextInt();
}
System.out.println("現(xiàn)在請(qǐng)輸入這些物品的價(jià)值:");
for (int i = 0; i < n; i++) {
v[i] = in.nextInt();
}
System.out.println("現(xiàn)在請(qǐng)輸入背包的容量:");
int c = in.nextInt();
/**
*按單位重量?jī)r(jià)值r[i]=v[i]/w[i]降序排列
*/
double[] r = new double[n];
int[] index = new int[n];
for (int i = 0; i < n; i++) {
r[i] = (double) v[i] / (double) w[i];
index[i] = i;
}
double temp = 0;
//降序排列
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (r[i] < r[j]) {
temp = r[i];
r[i] = r[j];
r[j] = temp;
//交換i溉贿，j的下標(biāo)
int x = index[i];
index[i] = index[j];
index[j] = x;
}
}
}
/**
*排序后的重量和價(jià)值分別存到w1[]和v1[]中
*/
int[] w1 = new int[n];
int[] v1 = new int[n];
int maxValue = 0;
for (int i = 0; i < n; i++) {
w1[i] = w[index[i]];
v1[i] = v[index[i]];
}
System.out.println(Arrays.toString(w1));
System.out.println(Arrays.toString(v1));
/**
*初始化解向量x[n]
*/
int[] x = new int[n];
for (int i = 0; i < n; i++) {
x[i] = 0;
}
/**
*求解并打印解向量
*/
for (int i = 0; i < n; i++) {
if (w1[i] < c) {
x[i] = 1;
c = c - w1[i];
maxValue += v1[i];
}
else{
x[i] = c/w[index[i]];
maxValue += x[i]*v[index[i]];
//break; 去掉這個(gè)就好
}
}
System.out.println("解向量是:" + Arrays.toString(x));
/**
*根據(jù)解向量求出背包中存放物品的最大價(jià)值并打印
*/
System.out.println("背包中物品的最大價(jià)值為:" + maxValue);
}
}
