本篇内容主要讲解“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]//等于上一次的值
else
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
完整代码如下:
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开始的话,可能会覆盖上一次的值,所以第二层循环的时候我们从后往前开始!
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();
}
}
到此,相信大家对“Java怎么实现背包动态规划”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。