POJ-1384 Piggy-Bank (完全背包)

题意：给出样例总数t,对应每个样例 给出 n,m对应空的最小重量以及满时的最大重量 然后给出硬币种类k，对应k种有对应的重量以及价值，求最小价值 思路：对应就是完全背包的问题： 有N种物品和一个容量为V的背包，每种物品都有无限件可用。 第i种物品的费用是c[i]，价值是w[i]。 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。　 这里背包的容量就为m-n,同时使求最小的价值，所以初始化dp为INF　　完全背包伪代码; for(int i=1; i<=n; i++) for(int j=w[i]; j<=V; j++)//刚好与01背包相反，这里是正序，而01背包为逆序 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

 

 

完整代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; int dp[10005]; int v[505],w[505]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); m -= n; for(int i=0;i<=m;i++){ dp[i] = INF; } int num; scanf("%d",&num); for(int i=1;i<=num;i++){ scanf("%d%d",&v[i],&w[i]); } dp[0] = 0; for( int i=1;i<=num;i++){ for(int j =w[i];j<=m;j++) dp[j]= min(dp[j],dp[j-w[i]]+v[i]); } if(dp[m]!=INF) printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]); else printf("This is impossible.\n"); } }

 

转载于:https://www.cnblogs.com/Tianwell/p/11213827.html

相关资源：JAVA上百实例源码以及开源项目