背包问题练习I NEED A OFFER! HDU 1203Piggy-Bank HDU 1114开心的金明洛谷 1060 小A点菜洛谷 1164采药洛谷 1048装箱问题洛谷 1049疯狂的采药洛谷 1616

66 阅读 0 评论 44 点赞

我是靠谱客的博主冷静康乃馨，最近开发中收集的这篇文章主要介绍背包问题练习I NEED A OFFER! HDU 1203Piggy-Bank HDU 1114开心的金明洛谷 1060 小A点菜洛谷 1164采药洛谷 1048装箱问题洛谷 1049疯狂的采药洛谷 1616，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背包问题就是典型的动态规划问题，这篇博客主要是针对，对背包问题进行一定的了解，简单的练习一下。

模板来自：https://blog.csdn.net/u012860063/article/details/32911251

I NEED A OFFER! HDU 1203

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1203

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 10005
//用概率论的思想1-不可能的结果，就是最大可能的结果
//01背包
double
f[N], b[N];
int a[N];
int main(){
int n, m;
while(scanf("%d %d", &n, &m) && (m || n)){
for(int i = 1; i <= m; i++){
scanf("%d %lf", &a[i], &b[i]);
b[i] = 1- b[i];
}
for(int i = 0; i <= n; i++){
f[i] = 1.0;
}
for(int i = 1; i <= m; i++){
for(int j = n; j >= a[i]; j--){
f[j] = min(f[j], f[j-a[i]]*b[i]);
}
}
printf("%.1lf%%n", (1- f[n]) *100);
}
return 0;
}

HDU 2191

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 105
//多重背包
int f[N], weight[N], price[N], amount[N];
int main(){
int T, n, m;
scanf("%d", &T);
while(T--){
scanf("%d %d", &n, &m);
memset(f, 0, sizeof(f));
for(int i = 0; i < m; i++){
cin>>price[i]>>weight[i]>>amount[i];
}
for(int i = 0; i < m; i++){
for(int k = 0; k < amount[i]; k++){
for(int j = n; j >= price[i]; j--){
f[j] = max(f[j], f[j-price[i]]+weight[i]);
}
}
}
cout<<f[n]<<endl;
}
return 0;
}

Piggy-Bank HDU 1114

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
//完全背包
#define N 10005
int w[N], f[N], p[N];
int main(){
int T, n, E, F;
cin>>T;
while(T--){
cin>>E>>F;
cin>>n;
int t = F - E;
for(int i = 0; i < n; i++){
cin>>p[i]>>w[i];
}
for(int i = 1; i <= t; i++)f[i] = 10000000;//更新比较小的一个
f[0] = 0;//必须的
for(int i = 0; i < n; i++){
for(int j = w[i]; j <= t; j++){
f[j] = min(f[j], f[j-w[i]] + p[i]);
}
}
if(f[t] != 10000000){
printf("The minimum amount of money in the piggy-bank is %d.n", f[t]);
}
else printf("This is impossible.n");
}
return 0;
}

开心的金明洛谷 1060

链接：https://www.luogu.org/problemnew/show/P1060

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 30005
//01背包
int f[N], v[N], p[N];
int main(){
int n, m;
cin>>n>>m;
for(int i = 0; i < m; i++){
cin>>v[i]>>p[i];
p[i] *= v[i];
}
for(int i = 0; i <= n; i++)f[i] = 0;
for(int i = 0; i < m; i++){
for(int j = n; j >= v[i]; j--){
f[j] = max(f[j], f[j-v[i]]+p[i]);
}
}
cout<<f[n]<<endl;
return 0;
}

小A点菜洛谷 1164

链接：https://www.luogu.org/problemnew/show/P1164

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
int f[N], a[N];
int main(){
int n, m;
cin>>n>>m;
for(int i = 0; i < n; i++)cin>>a[i];
for(int i = 0; i <= m; i++)f[i] = 0;
f[0] = 1;
for(int i = 0; i < n; i++){
for(int j = m; j >= a[i]; j--){
f[j] += f[j-a[i]];
}
}
cout<<f[m]<<endl;
return 0;
}

采药洛谷 1048

链接：https://www.luogu.org/problemnew/show/P1048

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
//01背包
int t[N], val[N], f[N];
int main(){
int T, M;
cin>>T>>M;
for(int i = 0; i < M; i++){
cin>>t[i]>>val[i];
}
for(int i = 0; i < M; i++){
for(int j = T; j >= t[i]; j--){
f[j] = max(f[j], f[j - t[i]]+val[i]);
}
}
cout<<f[T]<<endl;
return 0;
}

装箱问题洛谷 1049

链接：https://www.luogu.org/problemnew/show/P1049

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 20005
//01背包
int v[N], f[N];
int main(){
int V, M;
cin>>V>>M;
for(int i = 0; i < M; i++){
cin>>v[i];
}
for(int i = 0; i < M; i++){
for(int j = V; j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]]+v[i]);
}
}
cout<<V - f[V]<<endl;
return 0;
}

疯狂的采药洛谷 1616

链接：https://www.luogu.org/problemnew/show/P1616

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N
100005
//完全背包
int t[N], val[N], f[N];
int main(){
int T, M;
cin>>T>>M;
for(int i = 0; i < M; i++){
cin>>t[i]>>val[i];
}
for(int i = 0; i < M; i++){
for(int j = t[i]; j <= T; j++){
f[j] = max(f[j], f[j - t[i]]+val[i]);
}
}
cout<<f[T]<<endl;
return 0;
}