題干：

郵票分你一半

時間限制：1000?ms ?|? 內存限制：65535?KB

難度：3

描述

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

輸入

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

輸出

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

樣例輸入

2 5 2 6 5 8 9 3 2 1 5

樣例輸出

? ? ??? ?0

? ? ? ? ?2

解題報告：

? ? ? 這題看起來很簡單但是其實還是有坑的！下面提供n多中ac的代碼。坑就在于 ，sum有可能是奇數！！

AC代碼：（網絡版，至今不知為什么這么做可以，普通0-1背包）

#include<bits/stdc++.h>using namespace std; int n; int v[1000 + 5]; int dp[100000 + 5]; int main() {int t;int sum = 0;cin>>t;while(t--) {sum = 0;cin>>n;for(int i = 1; i<= n; i++) {scanf("%d",&v[i]);sum += v[i];}int yuan=sum;sum=(sum+1)/2;//這里直接sum=sum/2 也可以ac！！！即 +1與否不影響if(n == 1) {cout << v[1] << endl; continue;}memset(dp,0,sizeof(dp));for(int i = 1; i<=n; i++) for(int j = sum; j>=v[i]; j--) {if(abs(j-dp[j]) < abs(dp[j-v[i]]+v[i]-j)) dp[j]=dp[j];else dp[j]=dp[j-v[i]]+v[i];}cout << abs(yuan-dp[sum]-dp[sum]) << endl;}return 0 ;}

對于上面這種方法，我只理解到了下面的內容：

? ? ? 因為背包是一類問題，比如一般的0-1背包，你取dp[j] = max()，是因為你想得到價值最大的，所以你這個狀態代表的是，前i個物品在j容量下的最大價值是dp[j]這么大。?

? ? ? 所以對于這個題來說你想得到的是最接近一半的分值，所以你dp[j]中存的應該是最接近當前價值的， 即： 如果更接近當前價值，那我就更新他。

AC代碼2：（也是普通0-1背包）

#include<bits/stdc++.h>using namespace std; int n; int v[1000 + 5]; int dp[100000 + 5]; int main() {int t;int sum = 0;cin>>t;while(t--) {sum = 0;cin>>n;for(int i = 1; i<=n; i++) {scanf("%d",&v[i]);sum += v[i];}int half = sum>>1 ;//這里用half = sum>>1 + 1就錯了！！但是half = (sum+1)>>1是對的。。。當然你最后輸出的時候需要加個abs()才能ac！！！memset(dp,0,sizeof(dp));for(int i = 1; i<=n; i++) {for(int j = half; j>=v[i]; j--) {dp[j] = max(dp[j],dp[j-v[i]] + v[i]);}}cout << sum-2*dp[half]<<endl;} return 0 ;}

最開始就是這么寫的但是我的輸出相當于是cout << 2*(half - dp[half] )<<endl;樣例也過了，我也覺著我這樣理解是沒有問題的，舉個例子：總分值為10，我3他7，那我倆的差值不就是 ?2*((10/2)-3)這么大嗎？如果 ?我4他6，，也可以成立，然后就這么交上去了，然后wa。看了別人的代碼才發現，原來是奇偶數出現了問題，因為我試的樣例是偶數（10嘛），所以肯定看樣例肯定看不出來問題，于是我就改成了保留原sum，新開一個half，然后最后輸出的時候用sum去減，而不是2*half去減。也就是把最后的輸出改成了AC代碼中那樣的形式。

?

AC代碼3：（裝滿型0-1背包）

#include<bits/stdc++.h>using namespace std; int n; int v[1000 + 5]; int dp[100000 + 5]; int main() {int t;int sum = 0;cin>>t;while(t--) {sum = 0;cin>>n;for(int i = 1; i<=n; i++) {scanf("%d",&v[i]);sum += v[i];} // sum=(sum+1)/2;if(n == 1) {cout << v[1] << endl; continue;}memset(dp,-0x3f3f3f3f,sizeof(dp));dp[0] = 0;for(int i = 1; i<=n; i++) {for(int j = sum; j>=v[i]; j--) {dp[j] = max(dp[j],dp[j-v[i]] + v[i]);}}int minn = 0x3f3f3f3f;for(int i = sum; i>=0; i--) {if(dp[i] >=0) {//cout << 2*(sum-dp[i])<<endl;break;minn = min( abs(sum-dp[i]-dp[i]),minn);}}cout << minn<<endl;}return 0 ;}

這段代碼，是我在寫完AC代碼2，然后WA了之后，重新改了一下，不再有sum/=2這樣的操作，而是直接掃到sum，然后從后往前一個個的掃，維護一個minn，最后輸出minn，這樣也AC了但是時間是500ms左右，是AC代碼1，AC代碼2 的兩倍左右

總結

以上是生活随笔為你收集整理的【nyoj-456】 邮票分你一半 （dp，0-1背包的中点问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。