问题描述:
设U = {u1,u2,u3,......ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.
定义每个物品都具有两个属性weight和value.
我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.
一句话,让你的有限背包,装上最终总价值最高的物品。
注意,代码里面我加上了打印语句,可以用来查看算法的过程
- import java.util.Arrays;
- public class T {
-
- public static void knapsack(int[] value, int[] weight, int capicity, int[][] m) {
-
- int n = value.length - 1;
-
- int jMax = Math.min(weight[n] - 1, capicity);
-
- for (int j = 0; j <= jMax; j++)
- m[n][j] = 0;
- showArray(m);
-
-
- for (int j = weight[n]; j <= capicity; j++)
- m[n][j] = value[n];
- showArray(m);
-
- 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 showArray(int[][] m) {
- for (int[] a : m) {
- System.out.println(Arrays.toString(a));
- }
- System.out.println("-------------------------------------------");
- }
- public static void traceback(int[][] m, int[] w, int c, int[] x) {
- int n = w.length - 1;
- for (int i = 0; i < n; i++)
- if (m[i][c] == m[i + 1][c])
- x[i] = 0;
- else {
- x[i] = 1;
- c -= w[i];
- }
- x[n] = (m[n][c] > 0) ? 1 : 0;
- }
- public static void main(String[] args) {
-
- int[] ww = { 8,5,4,3 };
- int[] vv = { 10,7,5,4 };
- int[][] mm = new int[4][13];
- 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]);
- }
- }
分享到:
相关推荐
背包问题算法Java实现,实现了背包问题得到最大的价值,有压栈
背包算法 背包算法JAVA实现 背包算法JAVA实现
探究-贪心算法解决背包问题(Java实现)
用贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
用遗传算法解决多维背包问题,采用java代码。用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码。
使用蚁群算法实现了单维的01背包问题,自己写的,可直接运行AcoKP.java文件即可输出结果,收敛速度还可以,可根据自己需要修改参数
对于背包问题,用贪心算法用java将该问题进行了实现
算法设计,0-1背包问题,用java编写的贪心算法实现0-1背包问题。。
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
这个是背包算法。。解决背包问题的java代码。。。。。。。。。。。。。。。。。。。。。。
利用回溯算法解决0/1背包问题。类knapsack为背包类,bound是上界函数,函数bknapsack实现0/1背包回溯算法。内有详细注释。
本例采用java实现的0-1背包问题,采用的是回溯法,参考算法设计与分析(第二版)
背包问题九讲中的完全背包问题的三种算法的具体java实现代码。
0/1背包问题动态规划算法 一维数组实现 测试结果: 0 4 5 9 10 11 15 15 17 18 19 23 23 包负重为12时最优结果值为:23 包负重为1时最优结果物品组成:[w:1 v:4] 包负重为2时最优结果物品组成:[w:2 v:5] 包负重为3时...
0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
背包问题PSO(粒子群算法,Particle Swarm Optimization)基本算法代码,仅供参考
0/1背包问题的动态规划算法,使用java实现
原先在网上找到某位大虾写的一个简单的背包算法,于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合(其中的对象中只包含主键和值)和某个条件值,然后能打印sum(对象.值)条件的1个...