| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 8404 | Accepted: 4082 |
Description
Input
Output
Sample Input
3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4
Sample Output
The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.
题意：用一堆给定面值的硬币a1,a2,...,aN,(ai和aj的面值可以相同)，组合成恰好质量为W的最小总面值
思路：dp，设选择范围为前i个硬币组成质量恰好为j的最小面值为dp(i,j)=max(dp(i-1,j),dp(i-1,j-w[i])+p[i]),(j>=w[i])
边界：dp(i,j)=dp(i-1,j)，dp(i)(0)=0（总质量为0，总面值肯定为0)，初始化dp={INF},INF即总面值无限大，即没有合适的匹配方案;
小技巧：观察边界可令j直接从w[i]——>W，而不是从0——>W；利用滚动数组可直接将空间将为一维
C++代码：
//poj1384 dp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<ctype.h> using namespace std; const int maxn=510; const int INF=1000100; int T; int E,F; int N; int p[maxn],w[maxn]; int dp[INF]; int main() { cin>>T; while(T--){ cin>>E>>F>>N; for(int i=1;i<=N;i++){ cin>>p[i]>>w[i]; } for(int i=0;i<=F-E;i++) dp[i]=INF; dp[0]=0; for(int i=1;i<=N;i++){ for(int j=w[i];j<=F-E;j++){ dp[j]=min(dp[j-w[i]]+p[i],dp[j]); } } if(dp[F-E]!=INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[F-E]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }
Java代码:
//594ms import java.util.*; import java.io.*; public class Main { static final int maxn=510; static final int INF=1000100; public static int min(int a,int b){ return a<b?a:b; } public static void main(String[] args){ Scanner in=new Scanner(System.in); int T=in.nextInt(); while(T--!=0){ int E=in.nextInt(); int F=in.nextInt(); int N=in.nextInt(); int p[]=new int[N+1],w[]=new int[N+1]; for(int i=1;i<=N;i++){ p[i]=in.nextInt(); w[i]=in.nextInt(); } int dp[]=new int[F-E+1]; for(int i=0;i<=F-E;i++) dp[i]=INF; dp[0]=0; for(int i=1;i<=N;i++){ for(int j=w[i];j<=F-E;j++){ dp[j]=min(dp[j-w[i]]+p[i],dp[j]); } } if(dp[F-E]!=INF) System.out.println("The minimum amount of money in the piggy-bank is "+dp[F-E]+"."); else System.out.println("This is impossible."); } } }
原文：http://www.cnblogs.com/--560/p/4345855.html
