郵票分你一半

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

小珂最近收集了些郵票，他想把其中的一些給他的好朋友小明。每張郵票上都有分值，他們想把這些郵票分成兩份，并且使這兩份郵票的分值和相差最小（就是小珂得到的郵票分值和與小明的差值最小），現(xiàn)在每張郵票的分值已經(jīng)知道了，他們已經(jīng)分好了，你知道最后他們得到的郵票分值和相差多少嗎？ 輸入

第一行只有一個(gè)整數(shù)m（m<=1000),表示測(cè)試數(shù)據(jù)組數(shù)。
接下來(lái)有一個(gè)整數(shù)n(n<=1000)，表示郵票的張數(shù)。
然后有n個(gè)整數(shù)Vi(Vi<=100)，表示第i張郵票的分值。

輸出

輸出差值，每組輸出占一行。

樣例輸入

2 5 2 6 5 8 9 3 2 1 5

樣例輸出

0 2

背包問(wèn)題演變： ?
思路：?
以?xún)r(jià)值的總和的一半為背包容量，構(gòu)建0-1背包，
只要保證一半的背包容量裝的價(jià)值最大就行。
因?yàn)樽畲笠簿褪强們r(jià)值的一半。

#include<iostream> #include<cstring> using namespace std; int a[100010],b[100010]; int main() {int m,n,sum,i,j;cin>>m;while(m--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));/*第一次寫(xiě)時(shí)漏掉了數(shù)組初始化太大意了對(duì)于多組測(cè)試數(shù)據(jù)，每次輸入測(cè)試數(shù)據(jù)都要進(jìn)行初始化*/ sum=0;cin>>n;for(i=1;i<=n;i++){cin>>a[i];sum+=a[i];}for(i=1;i<=n;i++)for(j=sum/2;j>=a[i];j--)b[j]=(b[j]>b[j-a[i]]+a[i]?b[j]:b[j-a[i]]+a[i]); cout<<sum-2*b[sum/2]<<endl;}}

zb的生日

時(shí)間限制：3000?ms ?|? 內(nèi)存限制：65535?KB 難度：2 描述

今天是陰歷七月初五，acm隊(duì)員zb的生日。zb正在和C小加、never在武漢集訓(xùn)。他想給這兩位兄弟買(mǎi)點(diǎn)什么慶祝生日，經(jīng)過(guò)調(diào)查，zb發(fā)現(xiàn)C小加和never都很喜歡吃西瓜，而且一吃就是一堆的那種，zb立刻下定決心買(mǎi)了一堆西瓜。當(dāng)他準(zhǔn)備把西瓜送給C小加和never的時(shí)候，遇到了一個(gè)難題，never和C小加不在一塊住，只能把西瓜分成兩堆給他們，為了對(duì)每個(gè)人都公平，他想讓兩堆的重量之差最小。每個(gè)西瓜的重量已知，你能幫幫他么？ 輸入

多組測(cè)試數(shù)據(jù)（<=1500）。數(shù)據(jù)以EOF結(jié)尾
第一行輸入西瓜數(shù)量N (1 ≤ N ≤ 20)
第二行有N個(gè)數(shù)，W1, …, Wn (1 ≤ Wi ≤ 10000)分別代表每個(gè)西瓜的重量

輸出

輸出分成兩堆后的質(zhì)量差

樣例輸入

5 5 8 13 27 14

樣例輸出

3

深搜：

#include <stdio.h> #include <math.h> int a[21],sum,all,n,i,j,min; void dfs(int star) { if(star==n) return ; if(fabs(all-sum*2)<min)//差值最小。。如果這里不懂 動(dòng)動(dòng)手 原式轉(zhuǎn)換得到的 min=fabs(all-sum*2); for(int j=star;j<n;j++) { sum+=a[j]; dfs(j+1); sum-=a[j]; } } int main() { while(scanf("%d",&n)!=EOF) { all=0; for(i=0;i<n;i++) scanf("%d",&a[i]),all+=a[i]; min=n*10001; dfs(0); printf("%d\n",min); } }

DP:

#include<iostream> #include<cstring> using namespace std; int dp[100010],a[25];//dp中下標(biāo)值為當(dāng)前狀態(tài)西瓜總重量 int main() {int n;while(cin>>n){int sum=0;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i]; }for(int i=1;i<=n;i++)for(int j=sum/2;j>=a[i];j--)dp[j]=(dp[j]>dp[j-a[i]]+a[i]?dp[j]:dp[j-a[i]]+a[i]);//三目運(yùn)算符比max()函數(shù)更省時(shí) cout<<sum-2*dp[sum/2]<<endl;} }

用時(shí)很短的代碼詳見(jiàn)博客：http://blog.csdn.net/dgq8211/article/details/7720729

平臺(tái)最優(yōu)

#include <stdio.h> #define max(a,b) a>b?a:b int V,ans,n,w[21],sum[21]; void dfs(int i,int cnt) {if(i == 0){ans = max(ans,cnt);return ;}if(ans == V || cnt+sum[i] <= ans) //cutreturn ;if(cnt+w[i] <= V)dfs(i-1,cnt+w[i]);dfs(i-1,cnt); } int main() {while(~scanf("%d",&n)){ans = 0;for(int i=1;i<=n;i++){scanf("%d",&w[i]);sum[i] = sum[i-1] + w[i];}V = sum[n]/2;dfs(n,0);printf("%d\n",sum[n]-2*ans);}return 0; }

總結(jié)

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

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