当前位置: 首页 > news >正文

每日一题 494目标和(0-1背包)(灵神笔记)

0-1背包模版

有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?
当前操作?枚举第i个物品选还是不选,不选容量不变,选容量减少
子问题?从前i个物品中的最大容量和
下一个子问题?不选:剩余容量为c,前i-1个物品中的最大容量和;选:
剩余容量为c-w[i],前i个物品中的最大容量和

public int dfs(int i, int c) {if (i < 0) {return 0;}if (c < w[i]) {return dfs(i - 1, c);}return dfs(n - 1, capacity);}

题目

目标和
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2:

输入:nums = [1], target = 1
输出:1

提示:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

题解

记忆化搜索

class Solution {private int[] nums;private int[][] cache;public int findTargetSumWays(int[] nums, int target) {// p 正数的和// s nums的和// target = p - (s - p)// p = (s + t)/2//题目转化为从nums选择数使他们恰好等于(s + t)/2// 其中(s+t)必须为偶数for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;this.nums = nums;int n = nums.length;cache = new int[n][target + 1];for (int i = 0; i < n ; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1,target);}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 1 : 0;}if (cache[i][c] != -1) {return cache[i][c];}if (c < nums[i]) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);}
}

递推

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[n+1][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[i+1][c] = f[i][c];} else {f[i+1][c] = f[i][c] + f[i][c-nums[i]];}}}return f[n][target];}
}

空间优化(两个数组)

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[2][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[(i+1)%2][c] = f[i%2][c];} else {f[(i+1)%2][c] = f[i%2][c] + f[i%2][c-nums[i]];}}}return f[n%2][target];}
}

空间优化(一个数组)

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[] f = new int[target+1];f[0] = 1;for (int x : nums) {for (int c = target; c >= x; c--) {f[c] += f[c-x];}}return f[target];}
}
http://www.lryc.cn/news/176967.html

相关文章:

  • 软件测试工作步骤详情
  • java项目之列车票务信息管理系统(ssm源码+文档)
  • 【Pytorch笔记】3.数学运算
  • MeterSphere 监控方案
  • elementui-plus+ts+axios使用el-upload组件自定义上传
  • 【STM32单片机】u8g2智能风扇设计
  • Java中的IO流的缓冲流
  • 7、SpringBoot_高级配置
  • cocos2dx查看版本号的方法
  • 某高校的毕设
  • 利用uvicorn、Starlette和pipeline将一个训练好的大模型发布成一个web服务
  • 贝赛尔曲线 - Vue3实现加入购物车抛物线效果组件
  • AddressSanitizer failed to allocate 0xdfff0001000 (15392894357504) bytes解决方法
  • Fortinet 2023上半年全球威胁态势研究报告:勒索软件检测成下降趋势,针对性攻击持续升温
  • MySQL ——多表连接查询
  • 前沿技术 --> 待定
  • Linux定时python脚本(crontab版本)
  • 修改 Ubuntu .cache 和 pip cache 默认路径
  • 【Java SE】Lambda表达式
  • Kafka-UI
  • Unity 制作登录功能02-创建和链接数据库(SQlite)
  • 算法 岛屿数量-(递归回溯)
  • 安卓恶意应用识别(番外篇)(Python并行(多线程or多进程)执行cmd)
  • 基于大语言模型扬长避短架构服务
  • 初识网络编程
  • 轻松使用androidstudio交叉编译libredwg库
  • 【C++杂货铺】一颗具有搜索功能的二叉树
  • uni-app使用vue3,在元素或组件实例上添加ref,用this.$refs显示undefined
  • 蜂蜜配送销售商城小程序的作用是什么
  • 大数据Flink(八十四):SQL语法的DML:窗口聚合