admin管理员组文章数量:1531450
承上动态规划之01背包
问题G书架
Description
Farmer John最近为奶牛图书馆买了一个书架，但是书架很快就被填满了，现在唯一可用的地方就是最上面。
Farmer John有 N 头奶牛（1 ≤ N ≤ 20），每头奶牛都有一个高度 Hi（1 ≤ Hi ≤ 1000000，这些都是非常高的奶牛），书架的高度为 B（1 ≤ B ≤ S，其中 S 是所有奶牛的高度之和）。
为了达到书架的顶端，一头或多头奶牛可以站成一栋，这样它们的总高度就是各自身高的总和，这个总高度必须不低于书架的高度，这样奶牛才能到达顶部。
因为一栋那么高的奶牛，所以很必要，但也很危险，所以你的任务是找到一栋最小高度的奶牛让它们到达书架的上面。你的程序需要打印最佳奶牛栋和暑假之间的最小“多余”高度。
Format
Input
第一行，两个整数，N 和 B；
第二至第 N + 1 行，每一行包含一个整数 Hi。
Output
一个整数，表示奶牛的总高度和书架高度之间的最小差值（非负数）。
Samples
Sample Input 1
5 16
3
1
3
5
6
Sample Output 1
1
#include<bits/stdc++.h>
using namespace std;
long long n,m,v[25],dp[1000005],minn=1e9;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m*2;j>=v[i];j--)
{
dp[j]=max(dp[j-v[i]]+v[i],dp[j]);
}
}
for(int i=1;i<=m*2;i++)
{
if(dp[i]>=m) minn=min(dp[i],minn);
}
cout<<minn-m;
return 0;
}
//dp[n]=k为包里用了n个体积后 ，最大价值为k问题H天平
Description
Gigel有一个奇怪的天平，他想要平衡它。实际上，这个装置不同于其它普通天平。
该装置具有两个重量可以忽略不计的力臂，每只力臂的长度为 15。一些钩子连在这些力臂上。Gigel现在想 G（1 ≤ G ≤ 20）个砝码中的某些挂在力臂上，这些砝码的重量Wi在[1，25]范围内。Gigel必须要将这 G 个砝码全部挂完。
最后，Gigel利用自己在全国青少年信息学奥林匹克竞赛上获得的经验成功平衡了天平。现在他想知道有多少种方法可以实现。
保证每个测试点至少存在一种解决方案。
Format
Input
第一行两个整数 C（2 ≤ C ≤ 20）和 G（2 ≤ G ≤ 20）。其中 C 代表钩子的个数。
第二行包含 C 个整数（C 个数字各不相同且按照升序输入），每个整数范围为[-15，15]代表钩子相对于天平中心点的位置。（当没有配重时，天平是平衡的，即与坐标轴上 X 轴对齐， 距离的绝对值表示吊钩和平衡中心点之间的距离，数字的符号决定了吊钩所连接的力臂：左力臂为“ - ”，右力臂为“ + ”）。
第三行为 G 个不同的整数，按照升序输入，为砝码的重量，1 ≤ Wi ≤ 25。
Output
一行，一个整数 M，表示天平平衡的方案数。
Samples
Sample Input 1
2 4
-2 3
3 4 5 8
Sample Output 1
2#include<bits/stdc++.h>
using namespace std;
int c,g,a[25],b[25],dp[35][750005];
int main()
{
cin>>c>>g;
for(int i=1;i<=c;i++) cin>>a[i];
for(int i=1;i<=g;i++) cin>>b[i];
dp[0][7500]=1;
for(int i=1;i<=g;i++)
{
for(int j=0;j<=15000;j++)
{
for(int k=1;k<=c;k++)
{
dp[i][j]+=dp[i-1][j-b[i]*a版权声明：本文标题：动态规划之01背包练习 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1725585301a1031118.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论