P2842 题解

· · 题解

题目描述

### 解题思路 一眼 dp 题。dp 题的解题思路通常为：读懂题意，设计状态，确定目标态和初始态，思考转移方程，思考优化。 设计状态：$f[i]$ 表示凑出面值为 $i$ 至少需要的纸币张数。 目标态：$f[w]$；初始态：$f[0]=0$，因为凑出 $0$ 元一张纸币都不需要。 转移方程：$f[v]=\min\{f[v-a[i]]\}+1(i\in[1,n])

这是因为如果 v-a[i] 需要用 x 张纸币，那么只需要加上 a[i] 这一张纸币，就能用这 x+1 张凑出 v 了。

复杂度 O(nw)，因此不需要优化。

参考代码

注意：由于涉及到取 \min 操作，所以必须将初始值设为一个极大值。

#include<bits/stdc++.h>
using namespace std;
long long n,w,a[1010],f[100010];
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=10010;i++)f[i]=1145141919;
    for(int i=1;i<=n;i++)
        for(int j=a[i];j<=w;j++)
            f[j]=min(f[j],f[j-a[i]]+1);
    cout<<f[w]<<endl;
    return 0;
}