完全背包—洛—纸币问题 1

P2842 纸币问题 1

题目描述

某国有 \(n\) 种纸币，每种纸币面额为 \(a_i\) 并且有无限张，现在要凑出 \(w\) 的金额，试问最少用多少张纸币可以凑出来？（保证可以凑出对应金额）

输入格式

第一行两个整数 \(n,w\)，分别表示纸币的种数和要凑出的金额。
第二行一行 \(n\) 个以空格隔开的整数 \(a_1, a_2, a_3, \dots a_n\) 依次表示这 \(n\) 种纸币的面额。

输出格式

一行一个整数，表示最少使用的纸币张数。

输入输出样例 #1

输入 #1

6 15
1 5 10 20 50 100

输出 #1

2

输入输出样例 #2

输入 #2

3 15
1 5 11

输出 #2

3

说明/提示

对于 \(40\%\) 的数据，满足 \(n\le 10\)，\(w\le 100\)；
对于 \(100\%\) 的数据，满足 \(1\le n\le 10^3\)，\(1\le a_i , w\le 10^4\)。

思路

一开始犹豫了一下，不知道怎么凑面额，后来想到了背包问题，把每个面额想象成一个背包的容量，想到用完全背包，接下来就是想状态转移方程是什么，题目问最小数量纸币，每个纸币转移时就看数量，dp[w] = min(dp[w],dp[w-a[i]]+1)。

正解：

点击查看代码

#include <bits/stdc++.h>
using namespace std;
int n,w,a[1010];
int dp[10100];    //开w容量，不是n
int main()
{cin>>n>>w;for(int i = 1;i <= n;i++)    cin>>a[i];memset(dp,0x3f,sizeof(dp));         //赋初值，刚开始不可到达dp[0] = 0;for(int i = 1;i <= n;i++){for(int j = a[i];j <= w;j++){dp[j] = min(dp[j],dp[j-a[i]]+1);}}cout<<dp[w];
}
//唯一需要注意的是赋初值的时候所有容量赋成无穷大，dp[0] = 0。