题解 | #【模板】01背包#

【模板】01背包

https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e

优化一般就是优化状态转移方程

01背包
特点:每个物品仅能使用一次
重要变量&公式解释
f[i][j]:表示所有选法集合中,只从前i个物品中选,并且总体积≤≤j的选法的集合,它的值是这个集合中每一个选法的最大值.
状态转移方程
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])
f[i-1][j]:不选第i个物品的集合中的最大值
f[i-1][j-v[i]]+w[i]:选第i个物品的集合,但是直接求不容易求所在集合的属性,这里迂回打击一下,先将第i个物品的体积减去,求剩下集合中选法的最大值.
问题
集合如何划分

一般原则:不重不漏,不重不一定都要满足(一般求个数时要满足)

如何将现有的集合划分为更小的子集,使得所有子集都可以计算出来.
/*
1. f[i] 仅用到了f[i-1]层, 
2. j与j-v[i] 均小于j
3.若用到上一层的状态时,从大到小枚举, 反之从小到大哦
*/
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
        for(int j = m; j >= v[i]; j--) 
            f[j] = max(f[j], f[j-v[i]]+w[i]);
    cout << f[m] << endl;
 return 0;    
}



全部评论
Starting point Dynamic programming
点赞 回复 分享
发布于 2023-09-18 01:01 新疆
biu
点赞 回复 分享
发布于 2022-06-28 18:58

相关推荐

码砖:求职岗位要突出,一眼就能看到,教育背景放到最后,学校经历没那么重要,项目要重点突出
点赞 评论 收藏
分享
评论
9
6
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务