首页 > 代码库 > （背包dp）UVA - 562 Dividing coins

（背包dp）UVA - 562 Dividing coins

2024-08-11 17:09:28   218人阅读

题意：有n个硬币，每个硬币有个价值，两个人分配硬币，要求最公平分配时候两人拿到的钱的差。

分析：很明显，两人拿到的钱的差越小越公平。

一开始想，一定是一人一半最公平，所以直接把总和sum/2，对着half跑01背包，但是WA了，修改后分别讨论奇偶，额外进行一次sum-half的01背包，也WA，仔细想想觉得有些漏洞。

所以，这题其实可以干脆直接跑sum的背包，不断更新ans=min(ans,sum-dp[j]*2)就行了。如果ans==inf，表示不能分，也就是1个，这时输出0。

代码：

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<map>10 #include<list>11 #include<bitset>12 #include<string>13 #include<cctype>14 #include<cstdlib>15 16 using namespace std;17 18 typedef long long ll;19 typedef unsigned long long ull;20 21 int t;22 const int inf=1<<30;23 const int maxn=100*501;24 int dp[maxn];25 int val[110];26 27 void solve() {28     scanf("%d",&t);29     while(t--) {30         int n;31         int sum=0;32         memset(dp,0,sizeof(dp));33         scanf("%d",&n);34         for(int i=0; i<n; i++) {35             scanf("%d",&val[i]);36             sum+=val[i];37         }38         int half=sum/2;39         int ans=inf;40         for(int i=0; i<n; i++) {41             for(int j=sum; j>=val[i]; j--) {42                 dp[j]=max(dp[j],dp[j-val[i]]+val[i]);43                 ans=min(ans,abs(sum-dp[j]*2));44             }45         }46         if(ans==inf)puts("0");47         else printf("%d\n",ans);48 49     }50 }51 52 53 54 int main() {55 56 #ifndef ONLINE_JUDGE57     freopen("in.txt", "r", stdin);58     freopen("out.txt", "w", stdout);59 #endif60     //iostream::sync_with_stdio(false);61     solve();62     return 0;63 }

 

（背包dp）UVA - 562 Dividing coins


联系
我们