代码随想录算法训练营第四十一天 | 416. 分割等和子集，● 01背包问题，你该了解这些！ 滚动数组 ， 01背包问题，你该了解这些！

标签：01 weight nums int 材料 随想录 背包 bagweight dp

 

46. 携带研究材料（第六期模拟笔试） 时间限制：5.000S 空间限制：128MB

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例

5

提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

---

func test_2_wei_bag_problem1(weight, value []int, bagweight int) int { //dp[bgweight] 每个价值的空间，最大价值数 //递推公式， dp[i] = (dp[i],dp[i-weight(1)]+value) // 初始化， 第一列，0，到有空间就放一个位置 //遍历方式，双右到左 //输出结果 var dp []int dp = make([]int, bagweight+1) for i := 0; i < bagweight+1; i++ { if i >= weight[0] { dp[i] = value[0] } } for i := 1; i < len(weight); i++ { for j := bagweight; j >= 0; j-- { if j-weight[i] >= 0 && dp[j] < dp[j-weight[i]]+value[i] { dp[j] = dp[j-weight[i]] + value[i] } } } return dp[bagweight] }

---

 

46. 携带研究材料（第六期模拟笔试） 时间限制：5.000S 空间限制：128MB

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例

5

提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

---

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

func test_2_wei_bag_problem1(weight, value []int, bagweight int) int {
//dp[i][j] 第包括i前的物品，背包为j的最大值
//递推公式， dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[j]]+price[j])
// 初始化， 初始左列，与上行
//遍历方式，左到右，上到下
//输出结果
var dp [][]int
dp = make([][]int, len(weight))
for i := 0; i < len(dp); i++ {
dp[i] = make([]int, bagweight+1)
}
for i := 0; i < bagweight+1; i++ {
if i >= weight[0] {
dp[0][i] = value[0]
}
}
for i := 1; i < len(weight); i++ {
for j := 1; j < bagweight+1; j++ {
ans := dp[i-1][j]
if weight[i] <= j && ans < dp[i-1][j-weight[i]]+value[i] {
ans = dp[i-1][j-weight[i]] + value[i]
}
dp[i][j] = ans
}
}
return dp[len(weight)-1][bagweight]
}

func main() {
var m, n int
fmt.Scan(&m, &n)
materialSpaces := make([]int, m)
inputs := bufio.NewScanner(os.Stdin)
inputs.Scan() //每次读入一行
data := strings.Split(inputs.Text(), " ") //通过空格将他们分割，并存入一个字符串切片
for i := range data {
val, _ := strconv.Atoi(data[i]) //将字符串转换为int
materialSpaces[i] = val
}
inputs.Scan()
materialValues := make([]int, m)
data = strings.Split(inputs.Text(), " ") //通过空格将他们分割，并存入一个字符串切片
for i := range data {
val, _ := strconv.Atoi(data[i]) //将字符串转换为int
materialValues[i] = val
}

weight := materialSpaces
value := materialValues
res := test_2_wei_bag_problem1(weight, value, n)
fmt.Println(res)
}

---

416. 分割等和子集

  已解答 中等  

相关标签

相关企业  

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

---

//1. 难点1， 很难想到这是个背包问题 //2. 难点2， sum(nums)/2 这个背包容量 //3. 难点3， 因为容量==价格，所以n容量的最大价格就是n, 所以要永远取最大值, 最后判断是否为n，就是答案 func canPartition(nums []int) bool { //转化为0，1背包问题， nums[i] 即使价格，也是重要, 如果解为 sum(nums)/2 就是成功， sum(nums)/2 就是背包容量 var sumSize int for _, num := range nums { sumSize += num } if sumSize%2 == 1 { return false } packageSize := sumSize / 2 //dp公式， dp[i] 是不是能填充到dp[i]的大小 //递推公式， dp[i] = max(dp[i],dp[i-nums[i]]+nums[i]) //初始化，dp[i] 第一个数据的初始化 //从尾向前遍历 //输出 dp := make([]int, packageSize+1) for i := 0; i < len(dp); i++ { if i >= nums[0] { dp[i] = nums[0] } } for i := 1; i < len(nums); i++ { for j := packageSize; j >= 0; j-- { if j-nums[i] >= 0 && dp[j] < dp[j-nums[i]]+nums[i] { dp[j] = dp[j-nums[i]] + nums[i] } } } return dp[packageSize] == packageSize

标签：01,weight,nums,int,材料,随想录,背包,bagweight,dp
From： https://www.cnblogs.com/suxinmian/p/18066752