首页 > 【模板】01背包

xqxls

发表于 2021-10-28 17:02:11

题意整理。给定一个背包，能容纳体积为V。然后有n种物品，每种物品有一个对应的体积和价值。每种物品只提供一个。求这个背包最多能装多大价值的物品。如果背包恰好装满，最多能装多大价值的物品。方法一（动态规划） 1.解题思路第一问：状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的展开全文

其实是牛哥

发表于 2021-10-19 15:27:59

01背包难度：3星设 dp[i][j]dp[i][j]dp[i][j] 为前iii个物品，背包容量为jjj的最大价值。那么考虑第iii个物品是否放入，有两种情况：如果不放，那么等同于前i−1i-1i−1个物品，容量为jjj的背包的最优方案。如果放，那么等同于前i−1i-1i−1个物品，容展开全文

她似星辰划过天边

发表于 2022-02-15 17:51:25

经典dp问题整合了几位大佬的代码记录一下 #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int 展开全文

KEY.L

发表于 2022-06-27 21:59:49

优化一般就是优化状态转移方程 01背包特点:每个物品仅能使用一次重要变量&公式解释 f[i][j]:表示所有选法集合中,只从前i个物品中选,并且总体积≤≤j的选法的集合,它的值是这个集合中每一个选法的最大值. 状态转移方程 f[i][j] = max(f[i-1][j], f[i-1] 展开全文

bitmap

发表于 2022-03-01 16:48:36

import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc 展开全文

WaWaKing

发表于 2024-01-15 23:14:20

初始不装装入物品时的二维表示：f[0][0],f[0][1],...,f[0][V] 两种问题的主要区别：状态转移f[]的初始值不同。本题解主要讲解为什么要这样初始化。问题一：背包至少能装多大价值的物品背包可以不装满由于背包可以不装满，所以初始f[i][j]的i=0,j=1~V时，不管背展开全文

Coming680

发表于 2022-03-03 19:41:55

#include<iostream> #include<climits> using namespace std; struct node{ int val; int weight; }t[1001]; int dp[1001][1001] = {0}; in 展开全文

秋天Code

发表于 2023-08-31 13:00:12

每个物品只有放入、不放入两种情况，而且每个物品只能取一次，取背包的最大价值例题:P1048 [NOIP2005 普及组] 采药P1734 最大约数和P1060 [NOIP2006 普及组] 开心的金明二维数组模版 int n, m; cin >> n >> m; 展开全文

小牛向前冲_

发表于 2023-06-28 17:27:40

#include <iostream> #include <string.h> using namespace std; const int N = 1010; // 定义物品个数和背包体积，以及每个物品的对应的体积和价值，定义成全局可以直接初始化为0 int n, V, 展开全文

bibibibi

发表于 2021-11-07 16:21:59

描述有一个体积为VVV的背包，nnn个物体，每个物体的体积和价值分别为viv_ivi和wiw_iwi，每个物品仅可用一次，问: 背包能装的最大价值是多少？将背包装满后的最大价值是多少？思路 01背包的模板题，第一问答案为maxi≤Vdp[i]max_{i \leq V}dp[i]ma 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛