http://poj.org/problem?id=1384
完全背包是物品的个数是无限的。
二维数组：（这个题目用二维数组会超时）
由于dp数组初始化的问题，一直答案不对。
后面发现是：
for(int i=0;i<=N;i++)
dp[i][0]=0;
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iomanip> using namespace std; #define INF 10000000 int P[505],W[505];//每种硬币的金额，单个重量 int dp[505][10005]; int main() { int T; cin>>T; int E,F;//空的存钱罐的重量，装了硬币的存钱罐的重量 int N;//多少种不同的硬币 while(T--) { cin>>E>>F; cin>>N; int shiji=F-E; for(int i=1;i<=N;i++) cin>>P[i]>>W[i]; for(int i=0;i<=N;i++) for(int j=0;j<=shiji;j++) dp[i][j]=INF; for(int i=0;i<=N;i++) dp[i][0]=0; for(int i=1;i<=N;i++) for(int j=1;j<=shiji;j++) { if(j<W[i]) dp[i][j]=dp[i-1][j]; else { dp[i][j]=min(dp[i-1][j],dp[i][j-W[i]]+P[i]); } } if(dp[N][shiji]<INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[N][shiji]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }
一维数组：
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iomanip> using namespace std; #define INF 10000000 int P[505],W[505];//每种硬币的金额，单个重量 int dp[10005]; int main() { int T; cin>>T; int E,F;//空的存钱罐的重量，装了硬币的存钱罐的重量 int N;//多少种不同的硬币 while(T--) { cin>>E>>F; cin>>N; int shiji=F-E; for(int i=1;i<=N;i++) cin>>P[i]>>W[i]; for(int j=0;j<=shiji;j++) dp[j]=INF; dp[0]=0; for(int i=1;i<=N;i++) for(int j=W[i];j<=shiji;j++) { dp[j]=min(dp[j],dp[j-W[i]]+P[i]); } if(dp[shiji]<INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[shiji]<<"."<<endl; else cout<<"This is impossible."<<endl; } return 0; }
原文：https://www.cnblogs.com/h694879357/p/13767002.html