背包问题
【题目描述】
一个旅行者有一个最多能装 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]的值表示在此状态的最大价值
由此我们可以写出状态转移方程：
|
1 2 3 4 |
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]); |
完整代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.util.*;
public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m, n; int [] w = new int [ 35 ]; int [] v = new int [ 35 ]; m = in.nextInt(); n = in.nextInt(); int [][] dp = new int [ 35 ][ 205 ]; //m容量，n数目个数
for ( int i = 1 ; i <= n; i++) { w[i] = in.nextInt(); v[i] = in.nextInt(); }
for ( int i = 1 ; i <= n; i++) { for ( int j = 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 ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= m; j++) { System.out.print(dp[i][j]+ " " ); } System.out.println(); } System.out.println(dp[n][m]); in.close(); } } |
当然，如果容量数字和物品个数很大的时候，这个表会很大，但是dp数组只与自己的上一次有关，会造成空间浪费，所以我们可以改进成滚动数组，减小空间，使其变成一维数组。
小tips：因为是滚动数组，所以如果第二层循环从1开始的话，可能会覆盖上一次的值，所以第二层循环的时候我们从后往前开始！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.*; import java.lang.*;
public class Main { static int []dp= new int [ 205 ]; static int [] w = new int [ 35 ]; static int [] v = new int [ 35 ]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int m, n; m = in.nextInt(); n = in.nextInt(); // int[][] dp = new int[35][205];//m容量，n数目个数
for ( int i = 1 ; i <= n; i++) { w[i] = in.nextInt(); v[i] = in.nextInt(); }
for ( int i = 1 ; i <= n; i++) { for ( int j = m; j >= 1 ; j--) { if (j>=w[i]) { dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]); } }
} //输出dp数组 // for (int i = 1; i <= n; i++) { // for (int j = 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(); } } <br> |
以上就是java动态规划算法之背包问题的详细内容，更多关于java动态规划背包的资料请关注其它相关文章！
原文链接：https://blog.csdn.net/weixin_45440070/article/details/115450762
查看更多关于java背包问题动态规划算法分析的详细内容...