01背包问题的变形式

530 阅读 1 评论 0 点赞

原题链接：蓝桥杯2022年第十三届决赛真题-背包与魔法

```c
package 背包问题;

import java.util.Scanner;

public class 背包与魔法_01升级版 {
	private static int n,m,k;
	private static int w [];
	private static int v [];
	private static int dp [][][];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		w = new int [n+1];
		v = new int [n+1];
		dp = new int [n+1][m+1][2];
		for(int i = 1;i<=n;i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		//进行比较
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(j<w[i]) {	//当前重量 < 当前物品的重量
					dp[i][j][0] = dp[i-1][j][0];
					dp[i][j][1] = dp[i-1][j][1];
				}else {
					//可以取，但是要判断是否使用了魔法
					dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j-w[i]][0]+v[i]);
					
					//2.如果使用魔法
					dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-w[i]][1]+v[i]);
					if(w[i]+k<=j) {
						dp[i][j][1] = Math.max(dp[i][j][1],dp[i-1][j-w[i]+k][0]+v[i]*2);
					}
				}
			}
		}
		//==================================================
		System.out.println(Math.max(dp[n][m][0],dp[n][m][1]));
	
	}
}

```

0.0分

2 人评分

本文分类：题解列表
浏览次数：530 次浏览
发布日期：2023-04-07 12:09:58
本文链接：https://blog.dotcpp.com/a/95713

上一篇 > 最笨的方法
下一篇 > #C++2040——同学的等待

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

01背包问题的变形式

评论列表共有 1 条评论

发表评论取消回复

01背包问题的变形式

2876:矩阵交换行

2850:将输入的字符串转变成亲朋字符串

1029：自定义函数处理素数

就是数字有点大，我用的long 和%ld

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复