首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包

热度指数：26079 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 你有一个背包，最大容量为 $V$ 。现有 $n$ 件物品，第 $i$ 件物品的体积为 $v_i$ ，价值为 $w_i$ 。研究人员提出以下两种装填方案：
${\hspace{20pt}}_\texttt{1.}\,$ 不要求装满背包，求能获得的最大总价值；
${\hspace{20pt}}_\texttt{2.}\,$ 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 $0$ 。

输入描述:

第一行输入两个整数  和 ，分别表示物品数量与背包容量。 
此后  行，第  行输入两个整数 ，分别表示第  件物品的体积与价值。

输出描述:

输出两行： 
 第一行输出方案  的答案； 
 第二行输出方案  的答案（若无解输出 ）。

示例1

输入

输出

14
9

说明

在该组样例中： 
 选择第 、第  件物品即可获得最大价值 （未装满）； 
 选择第 、第  件物品可使背包体积  恰好装满且价值最大，为 。

示例2

输入

输出

8
0

说明

装第三个物品时总价值最大但是不满，装满背包无解。

备注:

要求  的时间复杂度， 空间复杂度。

算法知识视频讲解

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 展开全文

问题信息

难度：

27条回答 332收藏 2198浏览

通过挑战的用户

查看代码

苦闷的喜羊羊在求佛

2023-03-05 19:29:43
牛客71474...

2022-09-16 21:34:19
牛客72827...

2022-09-16 13:07:24
LaiNN

2022-09-16 11:34:21
不要香菜的小太...

2022-09-15 21:57:04

【模板】01背包

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题