一 . 0-1背包（基?。?问题：
去珠宝商店想要买一些魔法宝石 。商店里有 n 个宝石 ， 每个宝石的重量为 wi?，幸运值为 vi? 。的购物车只能装重量之和不超过 m的商品，现在她想知道如何选择宝石，能让购买的幸运值之和最大 。
输入格式
第一行两个整数 n,m ， 表示宝石的数量和购物车的承重能力 。
接下来 n行，每行两个整数 wi?,vi? ， 表示每个宝石的重量和幸运值 。
「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础 。动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i 个物品的做出决策，「0-1」正好代表不选与选两种决定 。每个物体只能用一次
二维：
#includeusing namespace std;const int MAXN=1005;int v[MAXN];//体积int w[MAXN];//价值int f[MAXN][MAXN]; //f[i][j]表示一种状态，即取n个宝石，体积不超过m时的最大幸运值int main(){int n,m;cin>>n>>m;for(int i=1; i<=n; i++){cin>>v[i]>>w[i];}//一维遍历物品看要不要拿，二维遍历背包容积 ， 然后在数组中存储该状态下的最优价值，//那么在判断下一个物品时就能直接使用该最优解for(int i=1; i<=n; i++) //遍历{for(int j=1; j<=m; j++){if(j
一维（由二维等价转换）：j表示背包容积，存储最优情况
#includeusing namespace std;const int MAXN=1005;int v[MAXN],w[MAXN];int f[MAXN];int main(){int n,m;cin>>n>>m;for(int i=1; i<=n; i++){cin>>v[i]>>w[i];}for(int i=1; i<=n; i++){for(int j=m; j>=v[i]; j--)//逆序,很重要?。。f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<
优化输入输出
#includeusing namespace std;const int MAXN = 1005;int f[MAXN];// int main() {int n, m;cin >> n >> m;for(int i = 1; i <= n; i++) {int v, w;cin >> v >> w;// 边输入边处理for(int j = m; j >= v; j--)f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;}
二 . 完全背包问题
和0-1背包问题类似 ， 不过是每个物品由只能用一次变成了能用多次 ， 代码也只有第二维 j 的访问
顺序不一样，二维到一维的简化过程较复杂，这里只写一维的代码
#includeusing namespace std;const int N=1005;int v[N],w[N];int f[N];int main(){int n,m;cin>>n>>m;for(int i=1; i<=n; i++){cin>>v[i]>>w[i];}for(int i=1; i<=n; i++){for(int j=v[i]; j<=m; j++) ///不同之处?。。。f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<
参考： 4. 在？0基础教你这道题目(会了点下赞) - ,题解,在？0基础教你这道题目(会了点下赞),
三 . 多重背包
文章插图
有 N 种物品和一个容量是 V 的背包 。
第 i 种物品最多有 si 件 ， 每件体积是 vi，价值是 wi 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大 。
输出最大价值 。
输入格式
第一行两个整数，N，V ， 用空格隔开，分别表示物品种数和背包容积 。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量 。
可以将其拆成0-1背包，比如将三件第一种物品拆分成一件一件的记录
#include using namespace std;int a[10005],b[10005],t=0,n,m,dp[10005]={ },w,v,s;int main(){cin>>n>>m;while(n--) //也可以for循环{cin>>v>>w>>s;while(s--){a[++t]=v; //将每个重量值放入新数组b[t]=w;}//把多重背包拆成01背包}for(int i=1;i<=t;i++)// 这里是小于t ， 不再是n，现在拆分后是t个物品for(int j=m;j>=a[i];j--)dp[j]=max(dp[j-a[i]]+b[i],dp[j]);//直接套01背包的板子cout<
【二 . 完全背包问题】参考链接：
