【算法】DP背包问题（C/C++）

个人主页：摆烂小白敲代码 创作领域：算法、C/C++ 持续更新算法领域的文章，让博主在您的算法之路上祝您一臂之力 欢迎各位大佬莅临我的博客，您的关注、点赞、收藏、评论是我持续创作最大的动力

背包问题是一类经典的DP类问题，通常一般会限定背包容量，物品的重量、价值。让你在有限的空间内选择的物品具有最大的价值。这一类的问题我们可以利用动态规划DP的思想进行解决，其效率也非常高

动态规划（Dynamic Programming，简称DP）是一种通过把复杂的原问题分解为相对简单的子问题的方式，进而求解原问题的方法。背包问题（Knapsack Problem）是动态规划中的经典问题之一，它有多种变体，其中有01背包、多重背包、完全背包、混合背包、二位费用背包、分组背包、有依赖的背包、树形背包等变形问题。

为什么说动态规划DP是解决背包问题的好方法，关键在于背包问题在于将问题进行分解为子问题，背包问题可以将背包容量进行分解，以最少的容量去装纳价值最高的物品，每一步的最优解，也就是每一步所能拿的价值最大，必然导致了最终整个背包的价值最大，在遍历物品时，我们定义的dp[i][j]为在前i件物品中背包容量为j所选择最大化，当i的不断增大，前面的状态必然被遍历过，且已经被求出来，这样后面我们便可以减少遍历次数，拿过来直接用即可。

0-1背包问题

问题描述：给定一组物品，每个物品都有一个重量和一个价值，现有一个背包可以承载的最大重量为W。问可以选择哪些物品，使得在不超过背包容量的前提下，所携带物品的总价值最大。 状态定义：dp[i][j] 表示从前i个物品中选取一些放入容量为j的背包中，能够获得的最大价值。 状态转移方程： 如果不取第i个物品，则 dp[i][j] = dp[i-1][j]，如果取第i个物品（前提是j >= w[i]），则 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 综上，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i] if j >= w[i]) 初始化：dp[0][j] = 0，即没有物品时，任何容量的背包价值都为0。 遍历顺序：先遍历物品，再遍历背包容量。

#include<stdio.h>
int f[100][100];//f[i][j]为在前i件物品中背包容量为j所选择最大化
int w[100],v[100];//w:物品重量，v:物品价值
int max(int x,int y){
	return x>y?x:y;
}
int main(){
	int i,j,n,m;//n为最大物品数，m为最大背包容量
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d%d",&w[i],&v[i]);
	}
	for(i=1;i<=n;i++){//i物品数，把所有物品遍历一遍，要么选要么不选
		for(j=1;j<=m;j++){//j背包容量
			if(w[i]>j){//第i个物品的重量大于此时背包容量j
				f[i][j]=f[i-1][j];//那就不选i
			}else{//如果小于背包容量就选
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
          //在前i-1个物品基础上，面对第i个物品，你选了，那就要付出w[i]的代价，来换取价值为v[i]
          //如果你没选i号物品，那么你还有j背包容量供你选择i号物品前面的物品
          //如果你选了i号物品，那么你的背包容量将减少w[i]，剩余j-w[i]供你选择i号物品前面的物品
          //因为是最优解问题，要寻找最大值，到底是选了i号物品价值更大还是不选i号物品价值更大
          //这里并不是选了就大，比如第i个物品是个石头，i-1是个钻石，你选了石头，钻石就放不开了，此时不选i号物品最优
			}
		}
	}
	printf("%d",f[n][m]);
}

完全背包问题

问题描述：给定一组物品，每个物品都有一个重量和一个价值，现有一个背包可以承载的最大重量为W。问可以选择哪些物品，使得在不超过背包容量的前提下，所携带物品的总价值最大。但每种物品可以无限取用。 状态定义：dp[i][j] 表示从前i个物品中选取一些放入容量为j的背包中，能够获得的最大价值。 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i] if j >= w[i])。即，对于每个物品i，我们考虑在当前背包容量j下，是否取用物品i，取用的话，可以取1个、2个...直到背包装不下为止。 初始化：dp[0][j] = 0，即没有物品时，任何容量的背包价值都为0。 遍历顺序：先遍历背包容量，再遍历物品。

多重背包问题

还有一种叫做多重背包问题，在多重背包问题中，每种物品都有限定的数量，不再是仅有一个，而是有多个。问题的描述如下： 给定一个背包容量为C，有n种物品，每种物品有重量w[i]、价值v[i]和数量s[i]。目标是选择物品放入背包，使得它们的总重量不超过背包容量，并且总价值最大。

这里不再详解，可以看我这一篇文章：细谈多重背包问题_n 种物品,每种物品有重量 w[i]、价值v[i],数量不限,背包容量为 b-CSDN博客

原题链接：细谈多重背包问题_n 种物品,每种物品有重量 w[i]、价值v[i],数量不限,背包容量为 b-CSDN博客

给定 V 种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

输入格式

第一行包含两个整数 V 和 N。

接下来的若干行，将一共输入 V 个整数，每个整数表示一种货币的面值。

输出格式

输出一个整数，表示所求总方案数。

数据范围

1≤V≤25, 1≤N≤10000 答案保证在long long范围内。

输入样例：

3 10
1 2 5

输出样例：

10

解题思路：

这道题纯纯就是模板题了，就是背包dp求方案数的一个模板，做acwing蓝桥杯每日一题以来，从来没有见过这么简单的题，话不多说，直接上代码！

#include<iostream>
using namespace std;
typedef long long ll;
int v,n;
const int N = 1e4+5;
int a[N];
ll dp[N];
int main(){
	cin>>v>>n;
	for(int i=1;i<=v;i++){
		cin>>a[i];
	}
	dp[0]=1;//什么也没有也是一种方案
	for(int i=1;i<=v;i++){//枚举逐渐加入第i类钱
		for(int j=1;j<=n;j++){//枚举容量
			if(j>=a[i]){
				dp[j]=dp[j]+dp[j-a[i]];
			}
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。