Problem P12. [算法课动态规划]背包问题
2022/9/10 1:24:52
本文主要是介绍Problem P12. [算法课动态规划]背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
01背包问题,每件物品都有放和不放这两种选择。
使用动态规划思想:有n件物品情况下的总价值最大背包和有n-1件物品情况下的总价值最大背包有关。
我也讲不大明白,对背包问题有兴趣的可以去这看看:https://zhuanlan.zhihu.com/p/93857890
#include<iostream> #include<bits/stdc++.h> #include<cstdio> using namespace std; int n; int cap; int dp[15]={0}; int w[5]={7,3,4,5}; int v[5]={42,12,40,25}; int main() { scanf("%d %d", &n, &cap); for (int i = 1; i <= n; i++){ //n件物品 for (int j = cap; j >= w[i]; j--){ //重量 dp[j] = max(dp[j], dp[j-w[i]]+v[i]); } } printf("%d", dp[cap]); return 0; }
这篇关于Problem P12. [算法课动态规划]背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署