2023年8月1日发(作者：)
Java背包问题求解实例代码背包问题主要是指⼀个给定容量的背包、若⼲具有⼀定价值和重量的物品，如何选择物品放⼊背包使物品的价值最⼤。其中⼜分01背包和⽆限背包，这⾥主要讨论01背包，即每个物品最多放⼀个。⽽⽆限背包可以转化为01背包。先说⼀下算法的主要思想，利⽤动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放⼊背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表⽰在前i个物品中能够装⼊容量为j的背包中的最⼤价值。则我们有下⾯的结果：（1），v[i][0]=v[0][j]=0;（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 = ; //物品个数
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;i<;i++){
f[i][0] = 0;
}
for(int i=0;i f[0][i] = 0; } //通过公式迭代计算 for(int i=1;i<;i++){ for(int j=1;j if(weight[i-1]>j) f[i][j] = f[i-1][j]; else{ if(f[i-1][j] f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; path[i][j] = 1; }else{ f[i][j] = f[i-1][j]; } //f[i][j] = (f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); } } } for(int i=0;i<;i++){ for(int j=0;j (f[i][j]+" "); } n(); } int i=-1; int j=f[0].length-1; while(i>0&&j>0){ if(path[i][j] == 1){ ("第"+i+"个物品装⼊ "); j -= weight[i-1]; } i--; } } } 输出：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 0 0 0 4 4 4 4 4 8 8 8 8 8 0 0 3 4 4 7 7 7 8 8 11 11 11 0 0 3 4 4 7 7 7 8 9 11 12 12 0 0 3 4 4 7 7 7 8 10 11 12 12 第4个物品装⼊ 第3个物品装⼊ 第1个物品装⼊ 以上⽅法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。先考虑上⾯讲的基本思路如何实现，肯定是有⼀个主循环i=1..N，每次算出来⼆维数组f[i][0..V]的所有值。那么，如果只⽤⼀个数组f[0..V]，能不能保证第i次循环结束后f[v]中表⽰的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个⼦问题递推⽽来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}⼀句恰就相当于我们的转移⽅程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上⾯的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另⼀个重要的背包问题P02最简捷的解决⽅案，故学习只⽤⼀维数组解01背包问题是⼗分必要的。我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将f[0..V]全部设为0。为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并⾮必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。2、⼀维数组法（⽆须装满）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 = ; //物品个数 int[] f = new int[m+1]; for(int i=0;i<;i++){ //不必装满则初始化为0 f[i] = 0; } for(int i=0;i for(int j=-1;j>=weight[i];j--){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } for(int i=0;i<;i++){ (f[i]+" "); } n(); n("最⼤价值为"+f[-1]); } } 输出0 0 3 4 4 7 7 7 8 10 11 12 12 最⼤价值为123、⼀维数组法（必须装满）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 = ; //物品个数 int[] f = new int[m+1]; for(int i=1;i<;i++){ //必装满则f[0]=0,]都初始化为⽆穷⼩ f[i] = _VALUE; } for(int i=0;i for(int j=-1;j>=weight[i];j--){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } for(int i=0;i<;i++){ (f[i]+" "); } n(); n("最⼤价值为"+f[-1]); } } 输出0 -2147483648 3 4 3 7 6 7 8 10 11 12 11 最⼤价值为11⼆、完全背包有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。但我们有更优的O(VN)的算法。O(VN)的算法这个算法使⽤⼀维数组，先看伪代码：for i=1..N for v=0..V f[v]=max{f[v],f[v-cost]+weight}你会发现，这个伪代码与P01的伪代码只有v的循环次序不同⽽已。public class test{ public static void main(String[] args){ int[] weight = {3,4,6,2,5}; int[] val = {6,8,7,5,9}; int maxw = 10; int[] f = new int[maxw+1]; for(int i=0;i<;i++){ f[i] = 0; } for(int i=0;i<;i++){ for(int j=weight[i];j<;j++){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } n(f[maxw]); } } 输出25总结以上就是本⽂关于Java背包问题求解实例代码的全部内容，希望对⼤家有所帮助。感兴趣的朋友可以继续参阅本站：、、等，如有不⾜之处，欢迎留⾔指出，⼩编会及时回复⼤家并进⾏修改，努⼒给⼴⼤编程⼯作及爱好者提供更优质的⽂章和更好的阅读体验。感谢朋友们对本站的⽀持！ 2023年8月1日发(作者：) Java背包问题求解实例代码背包问题主要是指⼀个给定容量的背包、若⼲具有⼀定价值和重量的物品，如何选择物品放⼊背包使物品的价值最⼤。其中⼜分01背包和⽆限背包，这⾥主要讨论01背包，即每个物品最多放⼀个。⽽⽆限背包可以转化为01背包。先说⼀下算法的主要思想，利⽤动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放⼊背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表⽰在前i个物品中能够装⼊容量为j的背包中的最⼤价值。则我们有下⾯的结果：（1），v[i][0]=v[0][j]=0;（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 = ; //物品个数 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;i<;i++){ f[i][0] = 0; } for(int i=0;i f[0][i] = 0; } //通过公式迭代计算 for(int i=1;i<;i++){ for(int j=1;j if(weight[i-1]>j) f[i][j] = f[i-1][j]; else{ if(f[i-1][j] f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; path[i][j] = 1; }else{ f[i][j] = f[i-1][j]; } //f[i][j] = (f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); } } } for(int i=0;i<;i++){ for(int j=0;j (f[i][j]+" "); } n(); } int i=-1; int j=f[0].length-1; while(i>0&&j>0){ if(path[i][j] == 1){ ("第"+i+"个物品装⼊ "); j -= weight[i-1]; } i--; } } } 输出：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 0 0 0 4 4 4 4 4 8 8 8 8 8 0 0 3 4 4 7 7 7 8 8 11 11 11 0 0 3 4 4 7 7 7 8 9 11 12 12 0 0 3 4 4 7 7 7 8 10 11 12 12 第4个物品装⼊ 第3个物品装⼊ 第1个物品装⼊ 以上⽅法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。先考虑上⾯讲的基本思路如何实现，肯定是有⼀个主循环i=1..N，每次算出来⼆维数组f[i][0..V]的所有值。那么，如果只⽤⼀个数组f[0..V]，能不能保证第i次循环结束后f[v]中表⽰的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个⼦问题递推⽽来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}⼀句恰就相当于我们的转移⽅程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上⾯的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另⼀个重要的背包问题P02最简捷的解决⽅案，故学习只⽤⼀维数组解01背包问题是⼗分必要的。我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将f[0..V]全部设为0。为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并⾮必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。2、⼀维数组法（⽆须装满）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 = ; //物品个数 int[] f = new int[m+1]; for(int i=0;i<;i++){ //不必装满则初始化为0 f[i] = 0; } for(int i=0;i for(int j=-1;j>=weight[i];j--){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } for(int i=0;i<;i++){ (f[i]+" "); } n(); n("最⼤价值为"+f[-1]); } } 输出0 0 3 4 4 7 7 7 8 10 11 12 12 最⼤价值为123、⼀维数组法（必须装满）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 = ; //物品个数 int[] f = new int[m+1]; for(int i=1;i<;i++){ //必装满则f[0]=0,]都初始化为⽆穷⼩ f[i] = _VALUE; } for(int i=0;i for(int j=-1;j>=weight[i];j--){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } for(int i=0;i<;i++){ (f[i]+" "); } n(); n("最⼤价值为"+f[-1]); } } 输出0 -2147483648 3 4 3 7 6 7 8 10 11 12 11 最⼤价值为11⼆、完全背包有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。但我们有更优的O(VN)的算法。O(VN)的算法这个算法使⽤⼀维数组，先看伪代码：for i=1..N for v=0..V f[v]=max{f[v],f[v-cost]+weight}你会发现，这个伪代码与P01的伪代码只有v的循环次序不同⽽已。public class test{ public static void main(String[] args){ int[] weight = {3,4,6,2,5}; int[] val = {6,8,7,5,9}; int maxw = 10; int[] f = new int[maxw+1]; for(int i=0;i<;i++){ f[i] = 0; } for(int i=0;i<;i++){ for(int j=weight[i];j<;j++){ f[j] = (f[j], f[j-weight[i]]+val[i]); } } n(f[maxw]); } } 输出25总结以上就是本⽂关于Java背包问题求解实例代码的全部内容，希望对⼤家有所帮助。感兴趣的朋友可以继续参阅本站：、、等，如有不⾜之处，欢迎留⾔指出，⼩编会及时回复⼤家并进⾏修改，努⼒给⼴⼤编程⼯作及爱好者提供更优质的⽂章和更好的阅读体验。感谢朋友们对本站的⽀持！
发布评论