首页 > 其他分享 >关于动态规划(Dynamic Programming)的若干思考 ------ [1.背包dp]

关于动态规划(Dynamic Programming)的若干思考 ------ [1.背包dp]

时间:2024-02-17 14:46:51浏览次数:29  
标签:const cout int Programming Dynamic maxn maxm ------ namespace

背包dp;

1.01背包
(1)

领域展开
#include<bits/stdc++.h>//simple
using namespace std;
const int maxm=2024;
int n,m;
int w[maxm],v[maxm],f[maxm][maxm];
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=0;j<=m;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>=v[i])
			f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);		
		}
	cout <<f[n][m];
	return 0;
} 

(2)
领域展开
#include<bits/stdc++.h>//optimize gundong
using namespace std;
const int maxm=2024;
int n,m;
int w[maxm],v[maxm],f[maxm][maxm];
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=0;j<=m;j++)
		{
			f[i&1][j]=f[(i-1)&1][j];
			if(j>=v[i])
			f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-v[i]]+w[i]);		
		}
	cout <<f[n&1][m];
	return 0;
} 
(3)
open
#include<bits/stdc++.h>
using namespace std;
const int maxn=3600;
int n,m;
int v[maxn],w[maxn],f[maxn];
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];
	return 0; 	          
}

标签:const,cout,int,Programming,Dynamic,maxn,maxm,------,namespace
From: https://www.cnblogs.com/lovey24/p/18017942

相关文章

  • 使用 Perlin 噪声来生成曲率线,然后根据曲率线生成高度图
      使用Perlin噪声生成曲率线,然后根据曲率线生成高度图的方法如下:生成Perlin噪声:首先,使用Perlin噪声算法生成一个二维的噪声图像。Perlin噪声是一种用于生成随机连续函数的算法,常用于生成自然风格的纹理和地形。通过调整Perlin噪声的参数,可以控制生成的噪声图像的特征和细......
  • P8784 [蓝桥杯 2022 省 B] 积木画
    原题链接太妙了,请移步题解区,有用数学归纳法做的,也有用找规律做的L型积木一定是成对出现的code#include<bits/stdc++.h>usingnamespacestd;constintmod=1e9+7;longlongdp[10000005]={0};intmain(){intn;cin>>n;dp[0]=1;dp[1]=1;dp[2]=2;......
  • T426130 酒
    本题题意说白了,给你\(a\)、\(b\)、\(c\)、\(d\)、\(e\)、\(x\)、\(y\),让你算出3个李白分别的酒量,算法由题知。最后,它让你输出这3个数中最大值的初始编号及其具体的值。代码如下:#include<bits/stdc++.h>usingnamespacestd;doublea,b,c,d,e,x,y;structp{ double......
  • 2024-02-17 有一个观点有松动了,没房没车没存款,配不配
       2024-02-17     好像挺根深蒂固的,没房没车没存款,都没有资格结婚恋爱,在女人面前也很自卑。   直到我叔和婶娘,跟我说,这个不讲配不配得上,而是讲缘分的。举了现实的例子,富家女嫁穷小伙的,帮穷小伙买车买房。   还有一些外省嫁过来的。还有我们家,几个叔......
  • Asp.Net Core访问阿里云MongoDB云数据库
    Asp.NetCore访问阿里云MongoDB云数据库选择.NetCore技术栈开发跨平台软件解决方案,投入少,产出快,有助于企业内部降本增效。MongoDB的实体类增加字段不用迁移数据库,适合需求经常变化的应用场景。如果是企业内部小型应用,拉一个MongoDB容器即可,如果要进一步考虑多节点冗余,高可用,异地......
  • [MRCTF2020]Easy_RSA
    [MRCTF2020]Easy_RSA首先,RSA计算的5个基本公式n=pqφ(n)=(p-1)(q-1)求φ(n)e*dmodφ(n)=1求ed其中之一c=m^emodn加密m=c^dmodn解密题目:importsympyfromgmpy2importgcd,invertfromrandomimportrandintfromCrypto.Util.numberimportgetPrime,is......
  • T426131 分配工资
    本题题意说白了就是,给你\(n\)个题,和出这次公开赛的工资\(m\),每个题都给出它的出题人和权重,问你编号为1的出题人能拿多少工资。本题中,工资要:按比分配!按比分配!!按比分配!!!所以代码如下:#include<bits/stdc++.h>usingnamespacestd;intn,x;doublem,a,b,y;intmain(){ c......
  • ASCII编码的诞生:解决字符标准化与跨平台通信的需求
    在计算机的发展过程中,字符的表示和传输一直是一个重要的问题。为了实现字符的标准化和跨平台通信,ASCII(AmericanStandardCodeforInformationInterchange)编码应运而生。Ascii编码解码|一个覆盖广泛主题工具的高效在线平台(amd794.com)https://amd794.com/asciiencordec......
  • IfcMaterialLayer
    IfcMaterialLayer 实体定义IfcMaterialLayer是由多个层(一个或多个)构成的元素的单个可识别部分。每个IfcMaterialLayer都具有恒定的厚度,并且沿着MlsBase相对于参考IfcMaterialLayerSet定位。 示例:使用三种IfcMaterialLayer:[1]砖、[2]气隙和[3]砖,对带有砖砌体且中间有气隙的......
  • HarmonyOS—状态管理概述
    在前文的描述中,我们构建的页面多为静态界面。如果希望构建一个动态的、有交互的界面,就需要引入“状态”的概念。图1效果图上面的示例中,用户与应用程序的交互触发了文本状态变更,状态变更引起了UI渲染,UI从“HelloWorld”变更为“HelloArkUI”。在声明式UI编程框架中,UI是程序......