首页 > 其他分享 >背包dp

背包dp

时间:2024-02-17 18:11:07浏览次数:25  
标签:背包 int bag 物品 dp define

01背包

描述:

有n个物品,每个物品只有一件,第i个物品体积为vi,价格为ci。现在有一个体积为V的背包,请你从n件物品里选出若干件放进背包里,使得背包里的物品价值最大。

思路:

01背包的特点是:每种物品只有一件,可以选择放或不放。我们可以根据此特点进行动态规划(DP),设f[i][j]表示前i件物品放入一个容量为j的背包中可以获得的最大价值,则易得状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

(详解:在“将前i个物品放入容量为j的背包中”的这个子问题中,由题意,我们只有
放或不放两种选择,那么就转化为一个只与前i-1个物品有关的问题。如果不放第i件物品,那么就是“前i-1件物品放入容量为j的背包中”,最大价值为f[i-1][j];如果放第i件物品,那么就是“前i-1件物品放入剩下的容量为j-c[i]的背包中”,最大价值为f[i-1][j-c[i]]+w[i])

由此可得01背包的最原始代码

coke
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=c[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
			}
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
} 
以上代码的时间和空间的复杂度均为O(V*N),其中时间已经不能进一步优化了,但是空间可以 滚动数组优化code
coke
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],ans=0;
int dp[2][N];//滚动数组优化 只开2行数组 
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			dp[i&1][j]=dp[(i-1)&1][j];
			if(j>=c[i]){
				dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-c[i]]+w[i]);
			}
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n&1][V];
	return Elaina;
}
一维优化code
coke
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],ans;
int dp[N];//一维数组优化
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=V;j>=c[i];j--){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

完全背包

描述:

设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。

思路:

完全背包的特点是:每种物品有无数件,可以选择放若干件或不放。
设k为取的物品的数量,依据01背包思路,易得状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-k * c[i]]+k * w[i])

coke
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			for(int k=0;k*c[i]<=j;k++){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*c[i]]+k*w[i]);
			}
		}
	}
}
int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
}

一维优化code

coke
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=c[i];j<=V;j++){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
	}
}
int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

多重背包

描述:

有N种物品和一个容量为V的背包。第i ii种物品最多有p[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

思路:

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有p[i]+1种策略:取0件,取1件……取p[i]件。令dp[i][j]表示前i种物品恰放入一个容量为j的背包的最大价值,则有状态转移方程:dp[i][j]=max(dp[i][j],dp[i-1][j-k * c[i]]+k * w[i])

coke
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],s[N];
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			for(int k=0;k<=s[i]&&k*c[i]<=j;k++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);
			}
		}
	}		            
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>s[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
}

一维优化code

coke
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],dp[N],s[N];
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=V;j>=0;j--){
				for(int k=0;k<=s[i]&&k*c[i]<=j;k++){
					dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
				}
			} 
	}		            
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>s[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

标签:背包,int,bag,物品,dp,define
From: https://www.cnblogs.com/hypixel/p/18018198

相关文章

  • 动态规划-DP 完整版
    动态规划学完了五大基础dp做个简单总结dp特征动态规划问题首要是找到做题的目的是求最大/小值还是其他;其二要确定问题的状态转移方程这是关键;第三为dp数组找到边界、最后检查是否需要结合其他相关知识如树dfs等;别忘了检查多测输入数组变量置零等易错点。......
  • 线性dp
    线性动态规划:不用多说,主要应用于求上升子序列,下降子序列等直接看例题:样例输入:13791638243718441921226315样例输出:max=879161819212263解:#include<bits/stdc++.h>usingnamespacestd;constintMAX=1050;intn,ans;intf[MAX],......
  • DP总结
    DP总结1.背包DP-0/1背包-完全背包-多重背包-分组背包-依赖背包-二维背包-树形背包DP0/1背包朴素版点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1010;//f[i][j]表示前i个物品,体积不超过j时的最大价值//不选第i个物品时,f[i][j]......
  • 回顾复习之线性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]<<......