及客户和

用户名：45374687

访问量：3665

签　名：

等　　级
排　　名	640
经　　验	4068
参赛次数	8
文章发表	11
年　　龄	19
在职情况	学生
学　　校	江苏某四非
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯基础练习VIP-Sine之舞-题解（C++代码）
浏览：158

1815: 蓝桥杯2014年第五届真题-排列序数
浏览：147

1433 危险系数较为省空间的解题方法
浏览：120

你可能喜欢

1643: 蓝桥杯算法训练VIP-最大体积完全背包问题变种

　　作者: 及客户和　　　　发表时间：2021-07-28 09:16:30 浏览：314　|　评论：0　

原题链接：蓝桥杯算法训练VIP-最大体积

解题思路:类似完全背包问题，如果序列中的数不互质，那么就有无限多个。
> 证明：设序列$${a_i}$$中的数的最大公约数为k(k≠1),则可设
$$a_1b_1+a_2b_2+. ..+a_nb_n=m$$，其中$${b_i}$$为正整数
即$$k(b_1\frac{a_1}{k}+b_2\frac{a_2}{k}+. ..+b_n\frac{a_n}{k})=m$$
> 
因为k是$${a_i}$$各项的最大公约数，所以$$\frac{a_1}{k},\frac{a_2}{k},. ..\frac{a_n}{k}$$均为正整数，所以m必为k的正整数倍，那么不是k的正整数倍的数（有无数个）都不能被表示。

如果互质，那么设dp[i]:i是否能被表示，显然dp[0]=1,dp[j]=dp[j]||dp[j-a[i]]
可以设一个很大的数MAX_WEIGHT，遍历时遍历到它即可。
注意事项:MAX_WEIGHT应设置得足够大，且应考虑到n==1的特殊情况，且以上证明过程**仅为充分条件**。

参考代码:
    #include <cstdio>
    #include <algorithm>
	
    const int M=11,MAX_WEIGHT=150001;
    using namespace std;
    bool dp[MAX_WEIGHT];
    int a[M];
    int gcd(int x,int y) {return (x%y==0)?y:gcd(y,x%y);}
    bool judge(int n) {
        int res=a[1];
        for(int i=2; i<=n; i++) {
            res=gcd(res,a[i]);
        }
		//注意考虑n==1 
        return res==1&&n!=1;
    }
    
    int main(){
        int n,sum=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        if(!judge(n))    printf("0");
        else {
            dp[0]=1;
            for(int i=1; i<=n; i++) {
                for(int j=a[i]; j<=MAX_WEIGHT; j++) {
                    dp[j]|=dp[j-a[i]];
                }
            }
            int i;
            for(i=MAX_WEIGHT; i>=0; i--) {
                if(!dp[i]) {
                    printf("%d",i);
                    break;
                }
            }
			//注意
            if(i<=0)    printf("0");
        }
        return 0;
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

及客户和

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

用筛法求之N内的素数。（C++代码）

母牛的故事（C语言代码）

C二级辅导-同因查找（C语言代码）

1643: 蓝桥杯算法训练VIP-最大体积完全背包问题变种

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

蛇行矩阵（C语言代码）

1011题解

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

及客户和

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

用筛法求之N内的素数。 （C++代码）

母牛的故事 （C语言代码）

C二级辅导-同因查找 （C语言代码）

1643: 蓝桥杯算法训练VIP-最大体积 完全背包问题变种

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

蛇行矩阵 （C语言代码）

1011题解

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

用筛法求之N内的素数。（C++代码）

母牛的故事（C语言代码）

C二级辅导-同因查找（C语言代码）

1643: 蓝桥杯算法训练VIP-最大体积完全背包问题变种

　　评论区

【金明的预算方案】（C++代码）

蛇行矩阵（C语言代码）

C二级辅导-进制转换（C语言代码）