背包问题刷题
P2840 纸币问题 2
有序排列 ： 顺序不同算同一种的，要先按照金额遍历，下一层循环就是遍历物品，这样可以保证每一层循环都可以遍历到所有物品；
步骤 枚举维度 正在处理什么 此时的 dp[3]代表什么j=3 跑所有纸币 最后一步可以加 1(来自 dp[2]的所有方案)包含 [1,1,1]、[2,1]j=3 跑所有纸币 最后一步可以加 2(来自 dp[1]的所有方案)新增 [1,2]无序排列 ： 顺序不同的算同一种，先按照物品遍历，再遍历金额，按种类依次加入，
1永远在2前面被考虑，所以{2, 1}这种顺序根本不会出现
步骤 枚举维度 正在处理什么 此时的 dp[3]代表什么i=1 (纸币 1) 只跑容量循环 只用 1 元凑数 只能由 1+1+1组成i=2 (纸币 2) 只跑容量循环 在 1 元的基础上尝试加入 2 元 只能由 1+1+1或1+2组成
状态方程和状态转移：
1. 状态定义
dp[i]表示凑出金额i的有序方案数。2. 状态转移方程
dp[j]=(dp[j]+dp[j−ak])modMOD
- 对于每个金额
j，遍历所有纸币a_k：
- 如果
j >= a_k，则dp[j]可以由dp[j - a_k]转移而来（在所有凑出j-a_k的方案末尾，加一张a_k纸币，得到新的有序方案）- 转移顺序：先枚举金额 j，再枚举纸币 a_k（这是区分有序 / 无序的关键！）
3. 初始化
dp[0] = 1：凑 0 元只有 1 种方式（不选任何纸币）- 其余
dp[i] = 04. 最终答案
dp[w]即为所求，对 109+7 取模。
有序：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 10010, mod = 1e9 + 7; ll v[N], f[N]; int n, w; int main(){ cin >> n >> w; for(int i=1; i<=n; i++) cin >> v[i]; // cout << v[1] << endl; f[0] = 1; for(int i = 1; i<=w; i++){ for(int j = 1; j<=n; j++){ if(v[j] <= i) f[i] = (f[i] + f[i-v[j]]) % mod; } } // cout << w << endl; cout << f[w]; return 0; }无序：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 10010, mod = 1e9 + 7; ll v[N], f[N]; int n, w; int main(){ cin >> n >> w; for(int i = 1; i<=n; i++) cin >> v[i]; for(int i = 1; i<=n; i++){ f[0] = 1; for(int j = v[i]; j<=w; j++){ f[j] = (f[j] + f[j-v[i]]) % mod; } } cout << f[w]; return 0; }