首页 > 其他分享 >DP总结

DP总结

时间：2024-02-17 17:37:24浏览次数：37  
标签：总结 背包 int 件物品 maxn using include DP

DP总结

1. 背包DP

-0/1背包
-完全背包
-多重背包
-分组背包
-依赖背包
-二维背包
-树形背包DP

0/1背包

朴素版

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

//f[i][j]表示前i个物品，体积不超过j时的最大价值
//不选第i个物品时，f[i][j] = f[i-1][j]
//选第i个物品时，f[i][j] = f[i-1][j-v[i]]+w[i],保证j>=v[i] 
int f[maxn][maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &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]);
		}
	}
	printf("%d", f[n][m]);

	return 0;
}

滚动数组版

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

int f[2][maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &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]);
		}
	}
	printf("%d", f[n&1][m]);

	return 0;

一维

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

int f[maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &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]);
		}
	}
	printf("%d", f[m]);

	return 0;
}

完全背包

朴素版
点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

//f[i][j]表示前i个物品，体积不超过j时的最大价值
//f[i][j]=max(f[i-1][j], f[i-1][j], f[i-1][j-v[i]]+w[i], f[i-1][j-2*v[i]]+2*w[i], ....)
int f[maxn][maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]); 
	
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=m; j++)
		{ 
			for(int k=0; k*v[i]<=j; k++)
			{
				f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
			}
		}
	}
	printf("%d", f[n][m]);

	return 0;
}
点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

//f[i][j]表示前i个物品，体积不超过j时的最大价值 
//f[i][j] = max(f[i-1][j], f[i][j-v] + w)
int f[maxn][maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &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][j-v[i]] + w[i]);
		}
	}
	printf("%d", f[n][m]);

	return 0;
}
一维
点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;

int f[maxn] = {};	//默认全为0，这样后面就不需要再初始化
int n = 0, m = 0;	//n件物品，m为背包总容量
int v[maxn] = {}, w[maxn] = {};	//v表示第i件物品体积，w为第i件物品价值

int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]); 
	
	for(int i=1; i<=n; i++)
	{
		for(int j=v[i]; j<=m; j++)
		{ 
			f[j] = max(f[j], f[j-v[i]] + w[i]);
		}
	}
	printf("%d", f[m]);

	return 0;
}

多重背包

点击查看代码

分组背包

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40;
const int maxm = 210;

//分组背包
int n = 0, m = 0, t = 0;	 
int v[maxn] = {}, c[maxn] = {};
//g[i][j]表示第i组第j个物品的编号
int g[15][maxn] = {};
//f[i][j]表示前i组物品，体积不超过j的最大价值
int f[15][maxm] = {};

int main()
{	 
	int x = 0;
	scanf("%d%d%d", &m, &n, &t); 
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d%d", &v[i], &c[i], &x);
		g[x][++g[x][0]] = i;
	}
	
	for(int i=1; i<=t; i++)
	{
		for(int j=0; j<=m; j++)
		{
			f[i][j] = f[i-1][j];
			for(int k=1; k<=g[i][0]; k++)
			{
				if(j >= v[g[i][k]]) 
				{
					x = g[i][k];
					f[i][j] = max(f[i][j], f[i-1][j-v[x]] + c[x]);	
				}
			}
		}
	}
	printf("%d", f[t][m]);

	return 0;
}
点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40;
const int maxm = 210;

//分组背包
int n = 0, m = 0, t = 0;	 
int v[maxn] = {}, c[maxn] = {}, g[15][maxn] = {};
int f[maxm] = {};

int main()
{	 
	int x = 0;
	scanf("%d%d%d", &m, &n, &t); 
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d%d", &v[i], &c[i], &x);
		g[x][++g[x][0]] = i;
	}
	
	for(int i=1; i<=t; i++)
	{
		for(int j=m; j>=0; j--)
		{
			for(int k=1; k<=g[i][0]; k++)
			{
				if(j >= v[g[i][k]]) 
				{
					x = g[i][k];
					f[j] = max(f[j], f[j-v[x]] + c[x]);	
				}
			}
		}
	}
	printf("%d", f[m]);

	return 0;
}

vector数组存最方便，也可用链式前向行

依赖背包

二维费用背包

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 60;
const int maxm = 410;

//二维费用背包
int n = 0, v = 0, m = 0;	 
int a[maxn] = {}, b[maxn] = {}, c[maxn] = {};
int f[maxm][maxm] = {};

int main()
{	 
	scanf("%d%d%d", &v, &m, &n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	}
	
	for(int i=1; i<=n; i++)
	{
		for(int j=v; j>=a[i]; j--)
		{
			for(int k=m; k>=b[i]; k--)
			{
				f[j][k] = max(f[j][k], f[j-a[i]][k-b[i]] + c[i]);
			}
		}
	}
	printf("%d", f[v][m]);

	return 0;
}

树形背包DP

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
int m,n,w[1005],f[1005][1005];
vector <int> a[1005];
void dp(int fa)
{
	for(int i=0;i<a[fa].size();i++)
	{
		int son=a[fa][i];
		dp(son);
		for(int j=n;j>=0;j--)	
			for(int k=0;k<=j;k++)
				f[fa][j]=max(f[fa][j],f[fa][j-k]+f[son][k]);
	}
	if(fa)
	{
		for(int j=n;j>0;j--)
			f[fa][j]=f[fa][j-1]+w[fa];
	}
}
int main()
{
	cin>>m>>n;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>w[i];
		a[x].push_back(i);
	}
	dp(0);
	cout<<f[0][n];
	return 0;
}

Vector

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
int m,n,w[1005],f[1005][1005];
vector <int> a[1005];
void dp(int fa)
{
	for(int i=0;i<a[fa].size();i++)
	{
		int son=a[fa][i];
		dp(son);
		for(int j=n;j>=0;j--)	
			for(int k=0;k<j;k++)
				f[fa][j]=max(f[fa][j],f[fa][j-k-1]+f[son][k]+w[son]);
	}

}
int main()
{
	cin>>m>>n;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>w[i];
		a[x].push_back(i);//x->i
	}
	dp(0);
	cout<<f[0][n];
	return 0;
}

链式前向星

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int f[200][200];
struct node{
	int from;
	int to;
	int w;
}edge[20000];
int head[2000];
void dfs(int zi,int gen){
	for(int i=head[zi];i;i=edge[i].from){
		int to=edge[i].to;
		dfs(to,zi);
		for(int j=m;j>=1;j--){
			for(int k=0;k<j;k++){
				f[zi][j]=max(f[zi][j],f[edge[i].to][k]+f[zi][j-k-1]+edge[i].w);
			}
		}
	}
}
void add(int from,int to,int w){
	cnt++;
	edge[cnt].from=head[from];
	edge[cnt].to=to;
	edge[cnt].w=w;
	head[from]=cnt;
}
int main(){
	int from,to,w;
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		cin>>from>>to>>w;
		add(from,to,w);
	}
	dfs(1,0);
	cout<<f[1][m];
}

oi-wiki树形背包DP 树形DP

点击查看代码 
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];

int dfs(int u) {
  int p = 1;
  f[u][1] = s[u];
  for (auto v : e[u]) {
    int siz = dfs(v);
    // 注意下面两重循环的上界和下界
    // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
    for (int i = min(p, m + 1); i; i--)
      for (int j = 1; j <= siz && i + j <= m + 1; j++)
        f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
    p += siz;
  }
  return p;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int k;
    scanf("%d%d", &k, &s[i]);
    e[k].push_back(i);
  }
  dfs(0);
  printf("%d", f[0][m + 1]);
  return 0;
}

注意事项：

标签：总结,背包,int,件物品,maxn,using,include,DP
From： https://www.cnblogs.com/wlesq/p/18018133

相关文章

  • 回顾复习之线性DP
    概念具有线性阶段划分的动态规划算法叫作线性动态规划（简称线性DP）。若状态包含多个维度，则每个维度都是线性划分的阶段，也属于线性DP，如下图所示：如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性DP。比如背包问题、区间DP、数位DP等都属于线性DP。例题求最......
  • 动态规划--一维dp和二维dp
    在解决背包问题时，使用一维动态规划数组和二维动态规划数组都是常见的方法，选择哪种方式取决于问题的特点和解法的需要。使用一维DP数组的情况：状态转移方程只涉及到上一行的元素：当状态转移方程只涉及到上一行的元素时，可以使用一维DP数组。这样能够降低空间复杂度，使算法更为简......
  • DP总结
    DP(动态规划)简介动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。DP基础1.必要前提需要满足三个条件：最优子......
  • 树形dp
    树形dp模型：给定一颗有n个节点的树，任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。基本思路：1.建树2.列出动态转移方程典型例题：没有上司的舞会#include<bits/stdc++.h>usingnamespacestd;intn,l,k,ans;vector<int>son[6600];intf[6600][2],v[6600],r......
  • 区间DP
    先看一下模板点击查看代码//f[i][j]表示从i到j区间的值for(intlen=2;len<=n;len++)//len表示区间长度{ for(inti=1;i+len-1<=n;i++)//关系一般为2<=i<=k<j<=n { intj=i+len-1;//j的求值，开始点+区间长度-1 for(intk=i;k<j;k++) { f[i][j]=min/max(状态转移......
  • 坐标DP
    坐标DP相较来说会比较简单。直接上例题1.坐标遍历问题传纸条点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=120;intm,n;intg[N][N],f[N][N][N];intans;intmain(){ cin>>n>>m; for(inti=1;i<=n;i++) { for(intj=1;j<=m;j++) { ......
  • 关于动态规划（Dynamic Programming）的若干思考 ------ [2.线性dp]
    线性dp的两个经典题目：最长上升子序列（LIS）and最长公共子序列（LCS）1.LIS核心代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2024;intcnt=0,ans=1;intf[maxn],a[maxn],c[maxn];voidout(intx){ if(x==0)return; out(c[x]); cout<<a[x]<<......
  • 线性dp
    基本应用：最长上升子序列：题目描述设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j)(i<>j)，若存在i1<i2<i3<…<ie且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的上升序列。例如13，7，9，16，38，24，37，18，44，19，21，22，63......
  • dp总结（背包，线性，区间，坐标，树形）
    背包dp0/1背包这种背包会提供可选的物品，背包的容积以及每件物品的价值，并且在选择物品是每件物品只有选一件或不选两种状态。例题输入4512243445输出8二维解法代码//状态转移方程为：f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])#include"bits/stdc++.h"using......
  • 坐标dp
    坐标dp典型例题：传纸条题目描述小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99