UVA.562 Dividing coins (DP 01背包)

2019-11-08 19:45:43

字体：大中小

来源：转载

供稿：网友

UVA.562 Dividing coins (DP)

题意分析

给出一堆不同面额的硬币，要求将这这些硬币分为价值接近的2堆（越接近越好，相等的情况最佳，且单个硬币不可再分），并最后输出这2堆硬币价值差值的绝对值。

先累加求出这堆硬币的总和sum，然后令sum/2为背包容量，所有硬币为商品做01背包即可。最后求出的解为其中一堆最多能分多少价值的硬币（设为x)，那么另一堆硬币的价值为sum-x，故两堆硬币的差值为sum-x*2。

核心状态转移方程： dp[i][j] = max(dp[i][j],dp[i-1][j-a[i]]+a[i])

代码总览

/* Title:UVA.562 Author:pengwill Date:2017-2-16*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 105#define mc 50000using namespace std;int a[nmax],dp[nmax][mc];int main(){ int t; scanf("%d",&t); while(t--){ int n,c = 0; scanf("%d",&n); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); for(int i = 1; i<=n; ++i) {scanf("%d",&a[i]); c+=a[i];} for(int i =1; i<=n;++i){ for(int j = 0;j<=c/2;++j){ dp[i][j] = dp[i-1][j]; if(j>=a[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-a[i]]+a[i]); } } PRintf("%d/n",c-2*dp[n][c/2]); } return 0;}

上一篇：UVA.10066 The Twin Towers (DP LCS)

下一篇：UVA.674 Coin Change (DP 完全背包)