个人主页：摆烂小白敲代码
创作领域：算法、C/C
持续更新算法领域的文章，让博主在您的算法之路上祝您一臂之力
欢迎各位大佬莅临我的博客，您的关注、点赞、收藏、评论是我持续创作最大的动力
背包问题是一类经典的DP类问题，通常一般会限定背包容量，物品的重量、价值。让你在有限的空间内选择的物品具有最大的价值。这一类的问题我们可以利用动态规划DP的思想进行解决，其效率也非常高
动态规划（Dynamic Programming，简称DP）是一种通过把复杂的原问题分解为相对简单的子问题的方式，进而求解原问题的方法。背包问题（Knapsack Problem）是动态规划中的经典问题之一，它有多种变体，其中有01背包、多重背包、完全背包、混合背包、二位费用背包、分组背包、有依赖的背包、树形背包等变形问题。
为什么说动态规划DP是解决背包问题的好方法，关键在于背包问题在于将问题进行分解为子问题，背包问题可以将背包容量进行分解，以最少的容量去装纳价值最高的物品，每一步的最优解，也就是每一步所能拿的价值最大，必然导致了最终整个背包的价值最大，在遍历物品时，我们定义的dpi为在前i件物品中背包容量为j所选择最大化，当i的不断增大，前面的状态必然被遍历过，且已经被求出来，这样后面我们便可以减少遍历次数，拿过来直接用即可。
0-1背包问题
问题描述：给定一组物品，每个物品都有一个重量和一个价值，现有一个背包可以承载的最大重量为W。问可以选择哪些物品，使得在不超过背包容量的前提下，所携带物品的总价值最大。 状态定义：dpi 表示从前i个物品中选取一些放入容量为j的背包中，能够获得的最大价值。 状态转移方程： 如果不取第i个物品，则 dpi = dpi-1，如果取第i个物品（前提是j >= wi），则 dpi = max(dpi-1, dpi-1j-wi] vi) 综上，dpi = max(dpi-1, dpi-1j-wi] vi if j >= wi) 初始化：dp0 = 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。问可以选择哪些物品，使得在不超过背包容量的前提下，所携带物品的总价值最大。但每种物品可以无限取用。 状态定义：dpi 表示从前i个物品中选取一些放入容量为j的背包中，能够获得的最大价值。 状态转移方程：dpi = max(dpi-1, dpij-wi] vi if j >= wi)。即，对于每个物品i，我们考虑在当前背包容量j下，是否取用物品i，取用的话，可以取1个、2个...直到背包装不下为止。 初始化：dp0 = 0，即没有物品时，任何容量的背包价值都为0。 遍历顺序：先遍历背包容量，再遍历物品。
多重背包问题
还有一种叫做多重背包问题，在多重背包问题中，每种物品都有限定的数量，不再是仅有一个，而是有多个。问题的描述如下：
给定一个背包容量为C，有n种物品，每种物品有重量wi、价值vi和数量si。目标是选择物品放入背包，使得它们的总重量不超过背包容量，并且总价值最大。
这里不再详解，可以看我这一篇文章：细谈多重背包问题_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范围内。
输入样例：
代码语言：javascript复制3 10
1 2 5输出样例：
代码语言：javascript复制10解题思路：
这道题纯纯就是模板题了，就是背包dp求方案数的一个模板，做acwing蓝桥杯每日一题以来，从来没有见过这么简单的题，话不多说，直接上代码！
代码语言：javascript复制#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;
}执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
