P2842 纸币问题 1

P2842 纸币问题 1

此题为背包问题的实际应用
定义dp[i]表示凑出i元花费的最少张数
首先我们要枚举每个纸币的面额

for(int i=1;i<=n;i++) //a[i]

然后可以进行一些基础的排除：
显然如果我们给出的金额(w)比枚举到的面额还要小 那就无法有该面额恰好凑出这个金额
于是判定条件+循环

for(int j=a[i];j<=w;j++)if(j>=a[i])

这里如果a[i]>w 就不会循环，省时省力
接下来推导递推式：
考虑dp[j]和a[i]
1.不选择a[i]这个面额：

dp[j]=dp[j]; //看起来像多余的一句...

2.选择a[i]这个面额

dp[j]=dp[j-a[i]]+1 //这是因为如果选择了a[i]，那就从金额为(j-a[i])的dp那里加上一张a[i]就好了

由于取最小值:

dp[j]=min(dp[j],dp[j-a[i]]+1)

ACcode:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,w;
int dp[10005];
int a[1005];
int main(){memset(dp,0x3f,sizeof(dp)); //取最小值初值要赋值为极大值dp[0]=0; //初始条件：凑出0元一张纸币也不用给cin>>n>>w;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)for(int j=a[i];j<=w;j++)if(j>=a[i])dp[j]=min(dp[j],dp[j-a[i]]+1);cout<<dp[w]<<endl;return 0;
}
//Author:AAA_jiancaipifa