本篇内容主要讲解“Java怎么实现背包动态规划”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Java怎么实现背包动态规划”吧!

背包问题

【题目描述】
一个旅行者有一个最多能装 MM 公斤的背包，现在有 nn 件物品，它们的重量分别是W1，W2，…,WnW1，W2，…,Wn,它们的价值分别为C1,C2,…,CnC1,C2,…,Cn，求旅行者能获得最大总价值。

【输入】
第一行：两个整数，MM(背包容量，M<=200M<=200)和NN(物品数量，N<=30N<=30)；

第2…N+12…N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。

【输出】
仅一行，一个数，表示最大总价值。

【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12

我们可以通过自己打表的方式找变化求得状态方程
（横向表示容量，j）(纵向表示第几个，i)
#1 2 3 4 5 6 7 8 9 10
1 0 1 1 1 1 1 1 1 1 1
2 0 1 3 3 4 4 4 4 4 4
3 0 1 3 5 5 6 8 8 9 9
4 0 1 3 5 5 6 9 9 10 12

dp[i][j]----i表示物品个数，j表示容量，dp[i][j]的值表示在此状态的最大价值
由此我们可以写出状态转移方程：

if(j<w[i])//当容量小于重量，即不拿的情况下dp[i][j]=dp[i-1][j]//等于上一次的值elsedp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

完整代码如下：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intm,n;int[]w=newint[35];int[]v=newint[35];m=in.nextInt();n=in.nextInt();int[][]dp=newint[35][205];//m容量，n数目个数for(inti=1;i<=n;i++){w[i]=in.nextInt();v[i]=in.nextInt();}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(j<w[i]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}}//输出dp数组for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){System.out.print(dp[i][j]+"");}System.out.println();}System.out.println(dp[n][m]);in.close();}}

当然，如果容量数字和物品个数很大的时候，这个表会很大，但是dp数组只与自己的上一次有关，会造成空间浪费，所以我们可以改进成滚动数组，减小空间，使其变成一维数组。

小tips：因为是滚动数组，所以如果第二层循环从1开始的话，可能会覆盖上一次的值，所以第二层循环的时候我们从后往前开始！

importjava.util.*;importjava.lang.*;publicclassMain{staticint[]dp=newint[205];staticint[]w=newint[35];staticint[]v=newint[35];publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intm,n;m=in.nextInt();n=in.nextInt();//int[][]dp=newint[35][205];//m容量，n数目个数for(inti=1;i<=n;i++){w[i]=in.nextInt();v[i]=in.nextInt();}for(inti=1;i<=n;i++){for(intj=m;j>=1;j--){if(j>=w[i]){dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);}}}//输出dp数组//for(inti=1;i<=n;i++){//for(intj=1;j<=m;j++){//System.out.print(dp[i][j]+"");//}//System.out.println();//}//System.out.println(dp[n][m]);System.out.println(dp[m]);in.close();}}

到此，相信大家对“Java怎么实现背包动态规划”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！