背包问题是一类经典的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; }
执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
文章知识点与官方知识档案匹配，可进一步学习相关知识
