题目大意:
将一对硬币分成两份,使得两份的总金额差最小。比如有三枚硬币,价值分别为2,3和5,则分成的两堆就是2,3一堆和 5一堆,它们的总金额差为0。
思路:
属于动态规划问题,刚开始看,想到了最大连续子序列和的问题,但又有点不一样。后来发现得用0-1背包来解决。定义一个数组dp[Max], Max要大一些,表示提供的硬币所能组成的所有和,dp[i]=1表示提供的硬币能够凑成 i , dp[i]=0表示凑不成 i , 这样从sum/2往下找,找到最大的,就是这些硬币所能凑成的总和最接近于sum/2的。
代码如下:
#include <iostream> #include <vector> #include <cstring> #include <string> #include <algorithm> using namespace std; int main() { freopen( "test.txt", "r", stdin ); int n, m, sum = 0, value, finalsum; vector<int> v; int T = 0; cin>>T; while( T-- ) { cin>>m; for( int i = 0; i < m; i++ ) { cin>>value; v.push_back(value); sum += value; } vector<int> dp(555555); dp[0] = 1; for( int i = 0; i < m; i++ ) { for( int j = sum; j>=v[i]; j-- ) { if( dp[j - v[i]] ) //若v[i]=2,则当j=2时,dp[0]=1,说明2能够由一个价值为2的硬币凑成。 dp[j] = 1; } } int tag = 0; for( int i = sum/2; i >= 0; i-- ) { if( dp[i] ) { tag = i; break; } } cout<<sum-2*tag<<endl; sum = 0; v.clear(); } return 0; }
相关推荐
Coin Change問題 計算錢幣兌換問題 有幾種可能
Dynamic Programming Solution to the Coin Changing Problem
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
Windows下编译利用openInventor进行可视化Geant4所需的Coin3D库文件(含coin-3.1.3和sowin-1.5.0)。原版本使用VS2010编译,经验证,VS2012也可以用,与Geant4版本无关。新版本修改如下: 1、修改了Coin3D\include\...
LeetCode-Coin-Change
Coin3D,Coin-3.1.3版,OpenGL封装类库,对场景、光照、对象捕捉、交互进行封装
Coin3D是开源三维图形开发库Open Inventor的三种实现之一,而Coin是开源代码Coin3D的核心库,本教程讲述了Windows系统下编译安装社区Coin代码的操作流程。
三维可视化Coin3d 罕见的中文教程,特别有利于三维建模程序研发
The binary files for Coin3DWinForm.
Coin-slider-master
coin3d第三方库,包含 simvoleon-2.0.3-msvc14-x64 quarter-1.0.1-msvc14-x64 sowin-1.6.0-msvc14-x64 soqt-1.6.0-msvc14-x64 simage-1.7.1-msvc14-x64 coin-4.0.0-msvc14-x64
Coin3D-Qt.PDF
COIN3D+帮助文件 COIN3D+帮助文件 COIN3D+帮助文件 COIN3D+帮助文件
1. 简介:Qt5+Coin3D实现简易版本的6自由度工业机器人建模仿真软件,鼠标拖动6个按钮可以分别控制6个轴转动。 2. 教程分为8个视频,每个视频长度不超过10分钟,基本涵盖介绍背景、Coin3D基础知识、Qt软件界面设计、...
Coin3D的参考手册 自己编译挺浪费时间的,还需要安装Doxygen 所以拿来分享。
环境:Qt4.8.6+VS2008+Coin3D3.1.3 语言:C++ 功能:检测两个物体之间的碰撞并打印出来;用户通过按钮可以控制是否进行检测。
这是sim coin3的三维开发的windows组件包。这些开发包你也可以到https://bitbucket.org/Coin3D/coin/downloads下载.OIV的主要参考书《 The Inventor Mentor 》可到网上下载
Open Inventor是目前世界上应用最为广泛的面向对象和交互式的三维图形软件开发包。SIM 开发的Coin3D是是Open Inventor三种实现之一。Coin是Coin3D的核心模块。文档根据最新Coin-4.01版本构建的chm格式开发帮助文档。
Coin Pusher Pro 1.17.0.unitypackage
免费Coin Metrics数据档案这些数据档案是使用免费的社区层生成的。 用于数据生成的位于目录中。可用数据CSV档案此数据类似于Coin Metrics。 档案: csv/<coin>.csv每个硬币的CSV文件,其中包含所有可用的免费指标带...