三人丿木丶一兀之

用户名：792408237

访问量：11639

签　名：

等　　级
排　　名	237
经　　验	6101
参赛次数	14
文章发表	36
年　　龄	0
在职情况	学生
学　　校	木星土里挖中心技术学院
专　　业

　　自我简介：

TA的其他文章

DNA-题解（Java代码）二维数组写法
浏览：225

IP判断-题解（Java代码）【详细分析】
浏览：237

Tom数-题解（Java代码）【详细介绍】
浏览：357

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

蓝桥杯算法提高VIP-01背包-题解（Java代码）

　　作者: 三人丿木丶一兀之　　　　发表时间：2020-10-14 10:39:17 浏览：243　|　评论：0　

原题链接：蓝桥杯算法提高VIP-01背包

![](/image_editor_upload/20201014103852_21008.png)

import java.util.Scanner;

public class 零一背包 {

/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();//物品的个数
		int wight=sc.nextInt();//背包能够装的重量
		int[][] wi=new int[n+1][2];
		for (int i = 1; i <=n; i++) {
			wi[i][0]=sc.nextInt();//背包的重量
			wi[i][1]=sc.nextInt();//背包的价值
		}
		//n+1：代表从第一个物品开始找最优价值
		//wight+1：代表从1-wight个不同重量能拥有的不同价值
		int[][] dp=new int[n+1][wight+1];
		//从第一个物品开始循环
		for (int i = 1; i <=n; i++) {
			//从重量为一开始找最优质量
			for (int j = 1; j <=wight; j++) {
				if (wi[i][0]>j) {
					//当物品重量大于J重量的包时，就为上面哪个最优的质量
					dp[i][j]=dp[i-1][j];
				}else if (wi[i][0]<=j) {
					//当该物品的重量满足J重量的包时
					//需判断它同重量下，上面的最优质量和它自身拥有的最优质量哪个大
					//自身拥有的质量为：你的质量+上一层你还剩余的重量j-w所还有的质量
					dp[i][j]=Math.max(dp[i-1][j], wi[i][1]+dp[i-1][j-wi[i][0]]);
				}
			}
		}
		//最后的商品个数以及最大的重量就是结果 即最下最右
		System.out.println(dp[n][wight]);
	}

}

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

三人丿木丶一兀之

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言训练-邮票组合问题* （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

蓝桥杯算法提高VIP-01背包-题解（Java代码）

评论区

精彩推荐

妹子杀手的故事（C语言代码）

字符串输入输出函数（Java代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1014题解

三人丿木丶一兀之

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言训练-邮票组合问题* （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

蓝桥杯算法提高VIP-01背包-题解（Java代码）

评论区

精彩推荐

妹子杀手的故事 （C语言代码）

字符串输入输出函数 （Java代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1014题解

　　评论区

妹子杀手的故事（C语言代码）

字符串输入输出函数（Java代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）