0-1背包问题 Java
2021/10/25 20:41:39
本文主要是介绍0-1背包问题 Java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
0-1背包问题 Java
package beiBao; /*0-1背包问题:给定n种物品和一个背包。物品i的重量是wi,其价值是vi,背包的容量为c。 * 问:哪些物品装入背包可使价值总和最大?最大是多少? * m(n,j)代表背包容量为j时,选择物品n时候的最优值 * m(i,j)代表背包容量为j时,选择物品从i,i+1,...n,时的最优解。 * 思路: * 价值:如果物品j的重量大于背包i重量,那么就舍弃,然后m[i][j] = m[i-1][j]; * 如果不大于呢,这个也有两个选择,可以装可以不装,条件是:Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]]),装了和不装里面选最大的 * 装还是不装记录:装:x[i] = 1;不装:x[i] = 0;判定条件:m[i][j] > m[i-1][j] 就把i装进去,反之不装。 * */ public class Knapsack { //c是背包容量,n是物品的个数,x[]是否装入:0不装入,1装入;w[]物品重量,v[]物品体积,m(i,j)代表背包容量为j时,选择物品从i,i+1,...n,时的最优解。 public static void KnapSack(int c,int n, int x[],int w[],int v[],int m[][]) { for(int i = 0;i <= n;i++) m[i][0] = 0;//背包容量为0 for(int j = 0;j <=c ;j++) m[0][j] = 0;//物品数量为0 for(int i = 1;i<=n;i++) { for(int j = 1;j<=c;j++) { if(w[i] > j)//物品i的重量大于背包总重量j,直接舍弃不装它 m[i][j] = m[i-1][j]; else m[i][j] = Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]]);//i的重量不大于j,也可以选择不装,也可以选择装 } } //下面是输出语句 System.out.println("表f的值");//打印换行 for(int i = 0;i <= n;i++) { for(int j = 0;j<=c;j++) System.out.printf("%-4d",m[i][j]);//遍历输出 System.out.println();//换行,做成表格 } int j = c;//背包容量等于c for(int i = n;i > 0;i--) {//物品从n开始遍历,选择要还是不要 if(m[i][j] > m[i-1][j] ){ x[i] = 1; j -= w[i];//每要一个物品,背包的总重量就要相应的减去这个物品的重量 } else x[i] = 0;//这个是不要物品 } System.out.println("表x的值:"); for(int i = 1;i<=n;i++) System.out.println("x" + i + "=" + x[i] +"\t");//这里输出要了哪个物品,没要哪个物品 System.out.println(); System.out.printf("总价值为:%d",m[n][c]);//总价值怎么出来的呢?这个 m[i][j] = Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]]); } public static void main(String[] args) { int c = 10; int n = 5; int x[] = new int[n + 1]; int w[] = new int [] {0,2,2,6,5,4}; int v[] = new int [] {0,6,3,5,4,6}; int m[][] = new int[n+1][c+1]; KnapSack(c, n, x, w, v, m); } }
这篇关于0-1背包问题 Java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)