7-4 贪吃的大嘴 (15分) 有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为m的小蛋糕,而且大嘴还特别懒,她希望通过吃数量最少的小蛋糕达到这个目的.所以她希望你能设计一个程序帮她决定要吃哪些小蛋糕.
输入格式: 先输入一行包含2个整数m、n,表示大嘴需要吃美味度和为m的小蛋糕,而小蛋糕一共有n种,下面输入n行,每行2个整数,第一个表示该种小蛋糕的美味度,第二个表示蛋糕店中该种小蛋糕的总数
输出格式: 输出一行包含一个整数表示大嘴最少需要吃的小蛋糕数量,若大嘴无法通过吃小蛋糕达到m的美味度和,则输出"><“.
输入样例: 在这里给出一组输入。例如：
10 2 4 1 2 10 输出样例: 在这里给出相应的输出。例如：
4 输入样例: 在这里给出一组输入。例如：
10 2 4 1 7 3 输出样例: 在这里给出相应的输出。例如：
<
题解：这是一个多重背包的问题。 两种解法 第一种 用dp代表，美味度为i时吃的最少的蛋糕块数量。 那么他的转移方程为 dp[k]=min(dp[k],dp[k-v[i]]+1); 一共有三重循环，分别代表蛋糕的种类数，每种蛋糕的数量以及对应的美味度时吃的最少的蛋糕数。 代码如下：
#include <bits/stdc++.h> #include <algorithm> #include<iostream> #include <stdio.h> #define INF 0x3f3f3f3f const int maxn=500005; using namespace std; typedef long long ll; int dp[maxn]; int a[maxn]; int v[maxn]; int main(){ int m,n,t,va; cin>>m>>n; memset(dp,INF,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>va>>t; //dp[va]=1; /* for(int k=1;k<=t;k++){ a[s+k]=v; } s+=t;*/ v[i]=va; a[i]=t; } //cout<<s<<endl;; dp[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=a[i];j++){ for(int k=m;k>=v[i];k--){ if(k-v[i]>=0){ //dp[i-a[j]*k]=k; dp[k]=min(dp[k],dp[k-v[i]]+1); } //if(k-a[i]==0) //f=1; //cout<<"i="<<k<<"dp[i]="<<dp[k]<<endl; } } } if(dp[m]!=INF) cout<<dp[m]<<endl; else cout<<"><"<<endl; return 0; }第二种方法：把这个多重背包转为为一个普通的0-1背包，多重背包是同一类有多个，那么只需要把同类的蛋糕一个个单独拿出来，此时的模型就变成了一个最简单的0-1背包。 代码
#include <bits/stdc++.h> #include <algorithm> #include<iostream> #include <stdio.h> #define INF 0x3f3f3f3f const int maxn=500005; using namespace std; typedef long long ll; int dp[maxn]; int a[maxn]; int v[maxn]; int main(){ int m,n,t,va; cin>>m>>n; memset(dp,INF,sizeof(dp)); int s=0; for(int i=1;i<=n;i++){ cin>>va>>t; //dp[va]=1; for(int k=1;k<=t;k++){ a[s+k]=va; } s+=t; } //cout<<s<<endl; dp[0]=0; for(int i=1;i<=s;i++){ for(int j=m;j>=a[i];j--){ dp[j]=min(dp[j],dp[j-a[i]]+1); } } if(dp[m]!=INF) cout<<dp[m]<<endl; else cout<<"><"<<endl; return 0; }