动态规划-举一反三
作者:
bking
,
2024-04-01 14:59:34
,
所有人可见
,
阅读 7
洛谷的纸币问题2,3
纸币问题3,n种货币凑出w金额的凑法(1+2和2+1是一种选法),这就是与货币系统那道题一模一样
纸币问题2,n种货币凑出w金额的凑法(认为1+2和2+1是一种选法)
并且问题2,3中的每种货币都可以用无限次
先聊一聊纸币问题3,与货币系统一样
#include<iostream>
using namespace std;
int a[1010];
int f[1010][10010];
int n,w;
long long mod = 1e9+7;
int main()
{
cin>>n>>w;
for(int i=0;i<=n;i++)f[i][0]=1;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=w;j++)
{
int k;
for(k=0;k*a[i]<=j;k++)
{
f[i][j]+=f[i-1][j-k*a[i]];
f[i][j]=f[i][j]%mod;
}
}
cout<<f[n][w];
return 0;
}
`
接着聊纸币问题2,可以发现是先枚举金额(一元一元的凑),在枚举货币的。
为啥枚举顺序是这样的呢?
先循环金额,在循环1-n每个货币,闫氏dp分析法,相当于把每个钱币都试着放在最后一个位置,每个钱币都放在最后,就是排列
样例: 2 6
1 5
1,5
5,1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
const int V = 1010;
const int M =1e9+7;
int n,v;
int a[V];
int f[N];
int cost;
int main()
{
cin>>v>>n;
for(int i=1;i<=v;i++)
{
cin>>a[i];
}
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=v;j++)
{
if(i>=a[j])
f[i]=(f[i]+f[i-a[j]])%M;
.........凑成i-a[j]元的所有方案
}
}
cout<<f[n]<<endl;
return 0;
}
#include <iostream>
using namespace std;
const int MAX_N = 1005;
const int MAX_W = 10005;
const int MOD = 1e9 + 7;
int n, w, a[MAX_N], f[MAX_W][MAX_N];
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
f[0][0] = 1;
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i][j - 1];
if (i - a[j] >= 0) {
f[i][j] = (f[i][j] + f[i - a[j]][j - 1]) % MOD;
}
}
}
cout << (f[w][n] % MOD) << endl;
return 0;
}
在这个特判条件下,确保了每个元素只能被选取一次,避免了重复计算.
当计算 f[4] 时,如果 4 - a[3] == a[3](这里a[3]=2)
根据前面的理解,这里f[4]+=f[4-a[3],表示
凑成4-a[3](2)的所有排列---a[3]放在最后一个位置
1 1, 2(a[3])
2(a[3]), 2(a[3])
所以特判为i - a[j] != a[j]
#include <iostream>
using namespace std;
const int MAX_N = 1005;
const int MAX_W = 10005;
const int MOD = 1e9 + 7;
int n, w, a[MAX_N], f[MAX_W];
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
f[0] = 1;
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= n; j++) {
if (i - a[j] >= 0 && i - a[j] != a[j]) {
f[i] = (f[i] + f[i - a[j]]) % MOD;
}
}
}
cout << (f[w] % MOD) << endl;
return 0;
}