完全背包入门题【简单到死啊】

声明：这些题大多是板子题，HDU的多，新手题都是，题目就不贴了，直接点链接就行

1. HDU- 1114 - Piggy-Bank

题意： 一个存钱罐，给你一开始体积和总共可以装的体积，然后在给你n 个硬币，给你相应的价值和体积，问你装满的话最少可以装多少钱，硬币可以用无限次
分析： 一个完全背包的板子题，直接看代码

参考代码

#include
using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int v[N],w[N],dp[N],s,e;ios_base::sync_with_stdio(0);int T;cin>>T;while(T--){int n;cin>>s>>e>>n;for(int i = 0;i < N;i++)dp[i] = INF;dp[0] = 0;for(int i = 0;i < n;i++){cin>>v[i]>>w[i];}for(int i = 0;i < n;i++){for(int j = w[i];j <= e-s;j++){dp[j] = min(dp[j],dp[j-w[i]]+v[i]);}}if(dp[e-s] == INF)puts("This is impossible.");else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[e-s]);}return 0;
}

2. HDU - 1248 - 寒冰王座

题意：只给你一个N元的钞票，让你求你最少浪费多少钱，你可以买三样东西价格分别为150,200,350，每个可以买无限次
分析：这个也是比较正的板子题，直接看代码

#includeusing namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int dp[N],a[5];
int main(){ios_base::sync_with_stdio(0);int T;cin>>T;a[0] = 150;a[1] = 200;a[2] = 350;while(T--){int n;cin>>n;for(int i = 0;i < N;i++)dp[i] = 0;for(int i = 0;i < 3;i++){for(int j = a[i];j <= n;j++){dp[j] = max(dp[j],dp[j-a[i]]+a[i]);}}cout<return 0;
}

3.HDU - 4508 - 湫湫系列故事——减肥记

题意：裸的完全背包，中文自己看就OK啦 oAo
参考代码：

#include
using namespace std;const int N = 1e5 + 10;
int dp[N],v[N],w[N];
int main(){ios_base::sync_with_stdio(0);int n;while(cin>>n){memset(dp,0,sizeof(dp));for(int i = 0;i < n;i++)cin>>v[i]>>w[i];int V;cin>>V;for(int i = 0;i < n;i++){for(int j = w[i];j <= V;j++){dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}cout<return 0;
}

待更新…………

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！