點(diǎn)擊打開(kāi)鏈接

點(diǎn)擊打開(kāi)鏈接兩道題其實(shí)是一樣的就是用平分后的01背包問(wèn)題；讓一方盡最大可能達(dá)到sum/2那這個(gè)差值就會(huì)轉(zhuǎn)化成最小，而我們想到的就是01背包問(wèn)題。

#include<stdio.h> #include<string.h> #define max(a,b) a > b ? a : b int f[100005],a[1005]; int main() {int n, t,i,sum;scanf("%d",&n);while(n--){ memset(f,0,sizeof(f));memset(a,0,sizeof(a));sum=0;scanf("%d",&t);for(i=1;i<=t;i++){scanf("%d",&a[i]);sum+=a[i];} int cout=sum/2;for(int j=1;j<=t;j++)for(i=cout;i>=a[j];i--) //注意i--不能從零到i++，不然會(huì)讓前面的賦值導(dǎo)致結(jié)果錯(cuò)誤f[i] = max(f[i],f[i-a[j]]+a[j]);int mark=sum-2*f[cout];printf("%d\n",mark);}return 0; } 突然覺(jué)得可以吧01背包的模板寫(xiě)一下，所以它就誕生了。

#include<stdio.h> #include<string.h> #define max(a,b) a > b ? a : b int f[100005],a[1005],t,cout; int bag() {for(int j=1;j<=t;j++) //t是所以物體的件數(shù)，就是讓所有的物品遍歷一遍,a[]是所裝的物品；for(int i=cout;i>=a[j];i--) //注意i--不能從零到i++，不然會(huì)讓前面的賦值導(dǎo)致結(jié)果錯(cuò)誤f[i] = max(f[i],f[i-a[j]]+a[j]);// cout是背包的最大容量，i代表的事背包容量的變化 return a[cout]; }

總結(jié)

以上是生活随笔為你收集整理的noj 邮票分你一半z的生日的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。