背包问题刷题

P2840 纸币问题 2有序排列 顺序不同算同一种的要先按照金额遍历下一层循环就是遍历物品这样可以保证每一层循环都可以遍历到所有物品步骤枚举维度正在处理什么此时的dp[3]代表什么j3跑所有纸币最后一步可以加 1(来自dp[2]的所有方案)包含[1,1,1]、[2,1]j3跑所有纸币最后一步可以加 2(来自dp[1]的所有方案)新增[1,2]无序排列 顺序不同的算同一种先按照物品遍历再遍历金额按种类依次加入1永远在2前面被考虑所以{2, 1}这种顺序根本不会出现步骤枚举维度正在处理什么此时的dp[3]代表什么i1 (纸币 1)只跑容量循环只用 1 元凑数只能由111组成i2 (纸币 2)只跑容量循环在 1 元的基础上尝试加入 2 元只能由111或12组成状态方程和状态转移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]即为所求对 1097 取模。有序#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 i1; in; i) cin v[i]; // cout v[1] endl; f[0] 1; for(int i 1; iw; i){ for(int j 1; jn; 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; in; i) cin v[i]; for(int i 1; in; i){ f[0] 1; for(int j v[i]; jw; j){ f[j] (f[j] f[j-v[i]]) % mod; } } cout f[w]; return 0; }