01背包抽象出来是有n种物品，每种物品只可以选一个或则零个如果爆搜的话会是\(2^n\)，但利用\(dp\)可以减少不必要的讨论模板AcWing2.01背包问题-AcWing没什么好分析的，主要是二维向一维的优化，先看看朴素版本#include<bits/stdc++.h>usingnamespacestd;constintMAXN

https://leetcode.cn/problems/coin-change-ii/description/可以直接考虑用完全背包的传统二维做法classSolution{publicintchange(intamount,int[]coins){//题意就是一个完全背包问题//f[i][j]表示前i个数中选,体积等于j的最大选法种数,答案就

原题链接：https://www.luogu.com.cn/problem/P1077题意解读：n种花选m个的选法，每种花数量为ai。解题思路：设dp[i][j]表示前i种花选j个的选法对于第i种花，可以选0,1,2...min(ai,j)个则有递推式：dp[i][j]=∑dp[i-1][j-k]，k取0,1,2...min(ai,j)初始化dp[0][0]=1100分代码：#incl

原题链接：https://www.luogu.com.cn/problem/P1866题意解读：N个整数M1~Mn，对每个整数Mi，选取1~Mi之间的一个数，使得N个数都不一样的选法。解题思路：将M1~Mn由小到大排序，第1个的选法有M1种第2个的选法有M2-1种第3个的选法有M3-2种......第n个选法有Mn-n+1种全部相乘取模即可。

本文思路来自伟大的@FxorGhere二分的单调性：如果\(mid\)可以，那么小于\(mid\)的也一定可以（从每排末尾剔除一些人即可）。主要问题是贪心的选法。原问题所引出的可能得选人的方案可能是离散的，比如：225当每排人数是2时，一下方案是一种最优解：1个身高为1的，1个身高为2的1个身高为1

5711取数-1状态表示：1维集合：前\(i\)个数里面选法和的最大值属性：Max状态计算：选或不选选：\(f(i-1)+a_i\) 不选：\(f(i-1)\)#include<iostream>usingnamespacestd;constintN=55;inta[N],f[N];intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>&

4.多重背包问题I-AcWing题库有\(N\)种物品和一个容量是\(V\)的背包。第\(i\)种物品最多有\(s_i\)件，每件体积是\(v_i\)，价值是\(w_i\)。求解将哪些物品装入

背包问题背包问题0/1背包问题完全背包多重背包二进制拆分法分组背包背包是线性DP中一类重要而特殊的模型，本文将其作为单独一部分进行总结整理。0/1背

01背包的重点即是状态转移方程让我们来一起过一遍题目：有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 v，价值是w。求解将哪些物品