背包九讲:https://blog.csdn.net/yandaoqiusheng/article/details/84782655/
这是一道完全背包模板题,但这道题的要求是拿最重的物品得到价值最小的钱币且要恰好等于背包容量,所以要将数组初始化为无穷大。
#include <iostream> #include<stdio.h> #include <cstring> #include <algorithm> #include <string.h> #include <queue> //#include <bits/stdc++.h> #define pb push_back #define qc std::ios::sync_with_stdio(0); #define maxn 0x3f3f3f using namespace std; const int max_n=35; typedef long long ll; typedef double dl; struct node{ int value,weight; }pig[505]; int dp[10005]; int main() { int t,n; int a,b; scanf("%d",&t); while(t--) { scanf("%d %d",&a,&b); int cnt=b-a; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d %d",&pig[i].value,&pig[i].weight); dp[0]=0; for(int i=1;i<=10000;i++) dp[i]=maxn; for(int i=1;i<=n;i++) for(int j=pig[i].weight;j<=cnt;j++) { dp[j]=min(dp[j],dp[j-pig[i].weight]+pig[i].value); } if(dp[cnt]==maxn) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[cnt]); } }