背包问题（动态规划看这一篇就够了）-Toy模板网

这篇具有很好参考价值的文章主要介绍了背包问题（动态规划看这一篇就够了）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

01背包问题

题目描述

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，他们的重量分别是W1，W2，......，Wn，他们的价值分别是C1,C2,......,Cn，求旅行者能获得的最大总价值。

输入

第一行：两个整数，M（M<=200）和N（N<=30）;
第2至N+1行：每行两个整数Wi，Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

样例输入

样例输出

思路

用数组dp[n][n]存储价值和重量关系，行表示取多少件物品，列表示分配多少容量
第0行和第0列设置为0，没有物体的时候价值没0，重量为0的时候物体无论多少价值也为0
如果第i个物体重量小于当前总重量j，则取前i-1和第i个物体组合的最优值，否则该物体不可以放进背包，取前i-1个物体的最优价值。

装入当前物体

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);//不取的价值与取的价值中更大的一者

不装入当前物体

dp[i][j]=dp[i-1][j];//取前i-1个物体的最优价值

背包问题（动态规划看这一篇就够了）,动态规划,算法

代码

#include <bits/stdc++.h>
using namespace std;
int w[50],c[50],dp[50][300];
int n,m;
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(j>=w[i])
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
			}
			else
			{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

完全背包问题

题目描述

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

输入

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；

第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

样例输入

样例输出

max=12

思路

01背包+枚举循环

代码

#include <bits/stdc++.h>
using namespace std;
int m,n,maxx;
int w[40],c[40],dp[40][250];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i];//输入 
	}
	for(int i=1;i<=n;i++)//枚举放几件物品 
	{
		for(int j=0;j<=m;j++)//枚举分配多少容量 
		{
			if(j<w[i])//如果放不下 
			{
				dp[i][j]=dp[i-1][j];//赋值为dp物品数-1的值 
			}
			else
			{
				for(int q=1;q*w[i]<=j;q++)//枚举放多少个 
				{
					dp[i][j]=max(dp[i-1][j],dp[i-1][j-q*w[i]]+q*c[i]);
				}
			} 
		}
	}
	cout<<"max="<<dp[n][m];
	return 0;
}

分组背包

题目描述

一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

输入

第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10)；
第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。

输出

仅一行，一个数，表示最大总价值。

样例输入

样例输出

思路

01背包+分组数组

z[a][b] a代表组号，b代表第几组的第几个文章来源地址https://www.toymoban.com/news/detail-852219.html

代码

#include <iostream>
using namespace std;
int v,n,t;
int w[35],c[35],p,z[20][35],dp[40][210];
int main()
{
	cin>>v>>n>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>c[i]>>p;
		z[p][0]++;
		z[p][z[p][0]]=i;//第几组的第几个
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=v;j++)
		{
			int maxx=-1;
			for(int k=1;k<=z[i][0];k++)
			{
				int l=z[i][k];
				if(j>=w[l])
				{
					maxx=max(maxx,dp[i-1][j-w[l]]+c[l]);
				}
			}
			maxx=max(maxx,dp[i-1][j]);
			dp[i][j]=maxx; 
		} 
	}
	cout<<dp[t][v];
	return 0;
}