我网上找了一段代码 解决背包问题
题目:
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 下面是代码:
红色的看不懂: /**
* @param value 价值
* @param weight 重量
* @param capicity 背包容量
* @param m 表示只有w[i],w[i+1]...w[n]这些物品时,背包容量为j时的最大价值
*/
public static void knapsack(int[] value, int[] weight, int capicity, int[][] m) {
// 数量
int n = value.length - 1;
// 最后一个重量-1和容量的更小的一个
int jMax = Math.min(weight[n] - 1, capicity);
// 将最后一个数组的前部分清空。
for (int j = 0; j <= jMax; j++)
m[n][j] = 0; // 当w[n]>j 有 m[n][j]=0
showArray(m);
// 后半部分设置为此物品的价值
// m[n][j] 表示只有w[n]物品,背包的容量为j时的最大价值
for (int j = weight[n]; j <= capicity; j++)
m[n][j] = value[n]; // 当w[n]<=j 有m[n][j]=v[n]
showArray(m);
// 递规调用求出m[][]其它值,直到求出m[0][c]
for (int i = n - 1; i >= 1; i--) {
jMax = Math.min(weight[i] - 1, capicity);
System.out.println(jMax);
for (int k = 0; k <= jMax; k++)
m[i][k] = m[i + 1][k];
showArray(m);
for (int h = weight[i]; h <= capicity; h++) {
// System.out.println(m[i + 1][h] + " / " + m[i + 1][h - weight[i]] + " + " + value[i]
// + "(" + h + "," + weight[i] + "," + value[i] + ")");
m[i][h] = Math.max(m[i + 1][h], m[i + 1][h - weight[i]] + value[i]);
}
showArray(m);
}
m[0][capicity] = m[1][capicity];
if (capicity >= weight[0])
m[0][capicity] = Math.max(m[0][capicity], m[1][capicity - weight[0]] + value[0]);
System.out.println("bestw =" + m[0][capicity]);
} public static void main(String[] args) {
// 测试
int[] ww = { 8, 5, 4, 9 };
int[] vv = { 10, 7, 5, 4 };
int[][] mm = new int[4][17];
knapsack(vv, ww, 12, mm);
// int[] xx = new int[ww.length];
// traceback(mm, ww, 12, xx);
// for (int i = 0; i < xx.length; i++)
// System.out.println(xx[i]);
}
public static void showArray(int[][] m) {
for (int[] a : m) {
System.out.println(Arrays.toString(a));
}
System.out.println("-------------------------------------------");
}
第一处红色部分看不懂?
第二处数组的4,17定义是任意的么?有什么限制
题目:
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 下面是代码:
红色的看不懂: /**
* @param value 价值
* @param weight 重量
* @param capicity 背包容量
* @param m 表示只有w[i],w[i+1]...w[n]这些物品时,背包容量为j时的最大价值
*/
public static void knapsack(int[] value, int[] weight, int capicity, int[][] m) {
// 数量
int n = value.length - 1;
// 最后一个重量-1和容量的更小的一个
int jMax = Math.min(weight[n] - 1, capicity);
// 将最后一个数组的前部分清空。
for (int j = 0; j <= jMax; j++)
m[n][j] = 0; // 当w[n]>j 有 m[n][j]=0
showArray(m);
// 后半部分设置为此物品的价值
// m[n][j] 表示只有w[n]物品,背包的容量为j时的最大价值
for (int j = weight[n]; j <= capicity; j++)
m[n][j] = value[n]; // 当w[n]<=j 有m[n][j]=v[n]
showArray(m);
// 递规调用求出m[][]其它值,直到求出m[0][c]
for (int i = n - 1; i >= 1; i--) {
jMax = Math.min(weight[i] - 1, capicity);
System.out.println(jMax);
for (int k = 0; k <= jMax; k++)
m[i][k] = m[i + 1][k];
showArray(m);
for (int h = weight[i]; h <= capicity; h++) {
// System.out.println(m[i + 1][h] + " / " + m[i + 1][h - weight[i]] + " + " + value[i]
// + "(" + h + "," + weight[i] + "," + value[i] + ")");
m[i][h] = Math.max(m[i + 1][h], m[i + 1][h - weight[i]] + value[i]);
}
showArray(m);
}
m[0][capicity] = m[1][capicity];
if (capicity >= weight[0])
m[0][capicity] = Math.max(m[0][capicity], m[1][capicity - weight[0]] + value[0]);
System.out.println("bestw =" + m[0][capicity]);
} public static void main(String[] args) {
// 测试
int[] ww = { 8, 5, 4, 9 };
int[] vv = { 10, 7, 5, 4 };
int[][] mm = new int[4][17];
knapsack(vv, ww, 12, mm);
// int[] xx = new int[ww.length];
// traceback(mm, ww, 12, xx);
// for (int i = 0; i < xx.length; i++)
// System.out.println(xx[i]);
}
public static void showArray(int[][] m) {
for (int[] a : m) {
System.out.println(Arrays.toString(a));
}
System.out.println("-------------------------------------------");
}
第一处红色部分看不懂?
第二处数组的4,17定义是任意的么?有什么限制
解决方案 »
- 关于如何快速删除一个本地txt文件的重复行?
- java高手帮忙加个东西
- windowClosing()在程序中是做什么用的,好象没有它也能结束程序.
- JAVA可以实现这个功能吗?
- 请问?Java中有没有方法可以把分散的图片合并成一张整图呢?
- 紧急求助:有人用JAVA写SOCKET从LINUX发协议到WINDOWS吗?
- java 运行程序的问题?
- 谁那有JBuilder6 Personal版的Serial Number 和 Key,我进不了Borland主页申请。
- 谁有JAVA的命名规范?
- 各位,我去书店看了看,觉得很难找到合适的java教材,我是初学者
- 关于列表简单程序,紧急求救!
- Java读取Excel文件问题
if (capicity >= weight[0])
m[0][capicity] = Math.max(m[0][capicity], m[1][capicity - weight[0]] + value[0]);
System.out.println("bestw =" + m[0][capicity]);这一处还有下面一处
int[][] mm = new int[4][17];
http://blog.csdn.net/nash_/article/details/8351611