Day46代码随想录(1刷) 多重背包+动态规划

2024-04-20 15:04

本文主要是介绍Day46代码随想录(1刷) 多重背包+动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

多重背包

多重背包就是物品数量不是只有一个也不是无限取而是有一个有限数量,我们可以把数量大过1的物品铺开也就是0-1背包问题了,所以多重背包可以转换成0-1背包

56. 携带矿石资源(第八期模拟笔试)

题目描述

你是一名宇航员,即将前往一个遥远的行星。在这个行星上,有许多不同类型的矿石资源,每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球,但你的宇航舱有一定的容量限制。 

给定一个宇航舱,最大容量为 C。现在有 N 种不同类型的矿石,每种矿石有一个重量 w[i],一个价值 v[i],以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下,最大化你所能获取的总价值。

输入描述

输入共包括四行,第一行包含两个整数 C 和 N,分别表示宇航舱的容量和矿石的种类数量。 

接下来的三行,每行包含 N 个正整数。具体如下: 

第二行包含 N 个整数,表示 N 种矿石的重量。 

第三行包含 N 个整数,表示 N 种矿石的价格。 

第四行包含 N 个整数,表示 N 种矿石的可用数量上限。

输出描述

输出一个整数,代表获取的最大价值。

输入示例
10 3
1 3 4
15 20 30
2 3 2
输出示例
90
提示信息

数据范围:
1 <= C <= 10000;
1 <= N <= 10000;
1 <= w[i], v[i], k[i] <= 10000;

状态:完成

思路:除了遍历物品和背包容量还要在里层把物品铺开就是要遍历物品数量转换成0-1背包,状态转移方程是:

                dp[j]=Math.max(dp[j],dp[j-k*weights[i]]+k*values[i]);

import java.util.*;
class Main{public static void main (String[] args) {/* code */Scanner sc=new Scanner(System.in);int C=sc.nextInt();int N=sc.nextInt();int[] weights=new int[N];int[] values=new int[N];int[] nums=new int[N];int[] dp=new int[C+1];for(int i=0;i<N;i++) weights[i]=sc.nextInt();for(int i=0;i<N;i++) values[i]=sc.nextInt();for(int i=0;i<N;i++) nums[i]=sc.nextInt();for(int i=0;i<N;i++){for(int j=C;j>=0;j--){for(int k=1;k<=nums[i];k++){if(j-k*weights[i]<0) continue;dp[j]=Math.max(dp[j],dp[j-k*weights[i]]+k*values[i]);}}}System.out.println(dp[C]);}
}

 198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

状态:完成

思路:这题比较简单,dp[i]表示这个房子时能偷走的最大价值,因为偷这个房子选不选取决于前一个房子和前两个房子,偷了上一家这家就不能偷,所以动态转移方程为:

                ​​​​​​​        dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);

class Solution {public int rob(int[] nums) {int[] dp=new int[nums.length];if(nums.length==1) return nums[0];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

 213. 打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

状态:自己没写出来看一下思路就写出来了。

思路:这题有环路所以判断就会变得麻烦所以我们可以拆成两个非环路进行比大小,对nums[0]进行讨论是否取,如果取则只能从[2,n-1)中讨论偷不偷,如果不取从[1,n)中讨论,所以最后只要比较两个环路的大小就ok了。

class Solution {public int rob(int[] nums) {int n=nums.length;if(n==1) return nums[0];if(n==2) return Math.max(nums[0],nums[1]);return Math.max(rob1(Arrays.copyOfRange(nums,1,n)),nums[0]+rob1(Arrays.copyOfRange(nums,2,n-1)));}public int rob1(int[] nums) {if(nums.length==0) return 0;int[] dp=new int[nums.length];if(nums.length==1) return nums[0];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

这篇关于Day46代码随想录(1刷) 多重背包+动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/920570

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n