蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级
2023-06-13 09:13:12 时间
/*问题描述 每个物品有一定的体积(废话),不同的物品组合,装入背包会战用一定的总体积。 假如每个物品有无限件可用,那么有些体积是永远也装不出来的。为了尽量装满背包, 附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解,如果是有限解, 保证不超过2,000,000,000 如果是无限解,则输出0 输入格式 第一行一个整数n(n<=10),表示物品的件数 第2行到N+1行: 每件物品的体积(1<= <=500) 输出格式 一个整数ans,表示不能用这些物品得到的最大体积。 样例输入 3 3 6 10 样例输出 17 */
#include<stdio.h>
#include<string.h>
int gcd(int a,int b)
{ if(b==0)return a;
else return gcd(b,a%b);
}
int main()
{
int n,t,i,m,a,b;long long int j,ans,t1;int s[20]; long int dp[80003];
scanf("%d",&n);
scanf("%d",&s[0]);
t=s[0];
for(i=1;i<n;i++)
{ scanf("%d",&s[i]);
t=gcd(t,s[i]);
if(s[i]<s[0]){int m=s[0];s[0]=s[i];s[i]=m;}
}
if(t==1&&s[0]!=1)
{ memset(dp,-1,sizeof(dp));t1=0;dp[0]=1;
for(i=0;i<n;i++)
for(j=s[i];j<80000;j++)
{if(dp[j-s[i]]!=-1)dp[j]=1;
if(i==n-1&&dp[j]==1)
{t1++;if(t1>=s[0])break;}
else t1=0,ans=j;
}
if(ans==79999)ans=s[0]-1;
printf("%ld\n",ans);
}
else printf("0\n");
return 0;
}
相关文章
- C语言中switch语句_switch在c语言中
- C语言中volatile关键字的使用
- C语言输出有颜色的字体
- 蓝桥杯 基础训练 完美的代价--------------C语言—菜鸟级
- 蓝桥杯算法训练 金陵十三钗(dp状态压缩)------C语言—菜鸟级
- 蓝桥杯 格子取数 (双线程 动态规划)-------C语言—菜鸟级
- ACM训练【排队买票】 (C语言描述 递归 5ms 过 简单易懂)--------C语言——菜鸟级
- C语言 分支循环
- C语言常用的字符串函数及案例
- 抽丝剥茧C语言(高阶)动态+文件通讯录
- [C语言] 数据结构-预备知识指针详解编程语言
- C语言代码规范(编程规范)
- 深入了解C语言中的MySQL语法(c 中mysql语法)
- C语言调用Oracle程序包的实践经验(c 调用oracle的包)
- 语言连接教程 MySQL的下载及C语言连接教程,帮助初学者快速掌握使用MySQL数据库,并学会用C语言连接MySQL数据库
- C语言中多维数组的内存分配和释放(malloc与free)的方法
- C语言柔性数组实例详解