Java背包问题求解实例代码-创新互联
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值大。其中又分01背包和无限背包,这里主要讨论01背包,即每个物品最多放一个。而无限背包可以转化为01背包。
专注于为中小企业提供成都做网站、成都网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业山阳免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了成百上千企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。先说一下算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的大价值。则我们有下面的结果:
(2),v[i][j]=v[i-1][j] 当w[i]>j
(3),v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 当j>=w[i]
好的,我们的算法就是基于此三个结论式。
一、01背包:
1、二维数组法
public class sf { public static void main(String[] args) { // TODO Auto-generated method stub int[] weight = {3,5,2,6,4}; //物品重量 int[] val = {4,4,3,5,3}; //物品价值 int m = 12; //背包容量 int n = val.length; //物品个数 int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的大价值 int[][] path = new int[n+1][m+1]; //初始化第一列和第一行 for(int i=0;ij) f[i][j] = f[i-1][j]; else{ if(f[i-1][j] 0&&j>0){ if(path[i][j] == 1){ System.out.print("第"+i+"个物品装入 "); j -= weight[i-1]; } i--; } } }
网页标题:Java背包问题求解实例代码-创新互联
文章源于:http://scyanting.com/article/dijpep.html