岳阳网站建设解决方案,软件开发工具与环境,移动端教学视频网站开发,广告联盟建设个人网站题干#xff1a;
邮票分你一半
时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB
难度#xff1a;3
描述 小珂最近收集了些邮票#xff0c;他想把其中的一些给他的好朋友小明。每张邮票上都有分值#xff0c;他们想把这些邮票分成两份#xff0c;并且使…题干
邮票分你一半
时间限制1000 ms | 内存限制65535 KB
难度3
描述 小珂最近收集了些邮票他想把其中的一些给他的好朋友小明。每张邮票上都有分值他们想把这些邮票分成两份并且使这两份邮票的分值和相差最小就是小珂得到的邮票分值和与小明的差值最小现在每张邮票的分值已经知道了他们已经分好了你知道最后他们得到的邮票分值和相差多少吗
输入
第一行只有一个整数mm1000),表示测试数据组数。 接下来有一个整数n(n1000)表示邮票的张数。 然后有n个整数Vi(Vi100)表示第i张邮票的分值。
输出
输出差值每组输出占一行。
样例输入
2
5
2 6 5 8 9
3
2 1 5
样例输出 0 2
解题报告 这题看起来很简单但是其实还是有坑的下面提供n多中ac的代码。坑就在于 sum有可能是奇数
AC代码网络版至今不知为什么这么做可以普通0-1背包
#includebits/stdc.husing namespace std;
int n;
int v[1000 5];
int dp[100000 5];
int main()
{int t;int sum 0;cint;while(t--) {sum 0;cinn;for(int i 1; i n; i) {scanf(%d,v[i]);sum v[i];}int yuansum;sum(sum1)/2;//这里直接sumsum/2 也可以ac即 1与否不影响if(n 1) {cout v[1] endl; continue;}memset(dp,0,sizeof(dp));for(int i 1; in; i) for(int j sum; jv[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背包
#includebits/stdc.husing namespace std;
int n;
int v[1000 5];
int dp[100000 5];
int main()
{int t;int sum 0;cint;while(t--) {sum 0;cinn;for(int i 1; in; i) {scanf(%d,v[i]);sum v[i];}int half sum1 ;//这里用half sum1 1就错了但是half (sum1)1是对的。。。当然你最后输出的时候需要加个abs()才能acmemset(dp,0,sizeof(dp));for(int i 1; in; i) {for(int j half; jv[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背包 #includebits/stdc.husing namespace std;
int n;
int v[1000 5];
int dp[100000 5];
int main()
{int t;int sum 0;cint;while(t--) {sum 0;cinn;for(int i 1; in; i) {scanf(%d,v[i]);sum v[i];}
// sum(sum1)/2;if(n 1) {cout v[1] endl; continue;}memset(dp,-0x3f3f3f3f,sizeof(dp));dp[0] 0;for(int i 1; in; i) {for(int j sum; jv[i]; j--) {dp[j] max(dp[j],dp[j-v[i]] v[i]);}}int minn 0x3f3f3f3f;for(int i sum; i0; i--) {if(dp[i] 0) {//cout 2*(sum-dp[i])endl;break;minn min( abs(sum-dp[i]-dp[i]),minn);}}cout minnendl;}return 0 ;}
这段代码是我在写完AC代码2然后WA了之后重新改了一下不再有sum/2这样的操作而是直接扫到sum然后从后往前一个个的扫维护一个minn最后输出minn这样也AC了但是时间是500ms左右是AC代码1AC代码2 的两倍左右
