URAL——1005 stone pile

浅浅的花香味﹌ 2022-08-10 18:29 5阅读 0赞

题意：

给你n个石头（1<=n<=20），给出每个石头的重量w\[i\]( 1<=w\[ i \] <= 100000),均分为两堆，求出两堆最小的差距重量，并输出。

这一题有两种解法，一时dfs搜出每种情况，二是动态规划求解问题。

#include<iostream>
    #include<stdlib.h>
    #define maxn 27
    #define INF 20000007
    using namespace std;
    long n,sum,ans,w[maxn];
    void dfs(long dep,long now)
    {
        if(dep>n)
        {
            if(ans>abs(now-(sum-now))) ans=abs(now-(sum-now));
            return;
        }
        dfs(dep+1,now);
        dfs(dep+1,now+w[dep]);
    }
    int main()
    {
        cin>>n;
        sum=0;
        for(long i=1;i<=n;i++)
        {
            cin>>w[i];
            sum+=w[i];
        }
        ans=INF;
        dfs(1,0);
        cout<<ans<<endl;
    return 0;
    }

复杂度为2^n,因为n值很小，此方法对这一题求解较优

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cstdlib>
    #define N 1000010
    int w[22],object[N];
    using namespace std;
    int main()
    {
    	int n;
    	while(scanf("%d",&n)==1)
    	{
    		int sum=0,half,i,j; 
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&w[i]);
    			sum+=w[i];
    		}
    		half=sum/2;
    		 for (i=1;i<=n;i++)
            {
            	for (j=half;j>=w[i];j--)
                    object[j] = max(object[j], object[j-w[i]]+w[i]);
            }
            cout<<sum-object[half]*2<<endl;
    	}
    	 return 0;
    }

复杂度在重量很大的情况下同样达百万级别，但是因为开数组浪费了内存。关于动态规划01背包问题，推荐看一下

《背包问题九讲》[http://love-oriented.com/pack/Index.html\#sec4][http_love-oriented.com_pack_Index.html_sec4]

[http_love-oriented.com_pack_Index.html_sec4]: http://love-oriented.com/pack/Index.html#sec4

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关【BZOJ 2138】stone

Problem Description 话说 \\(Nan\\) 在海边等人，预计还要等上 \\(M\\) 分钟。为了打发时间，他玩起了石子。 \\(Nan\\)

浅浅的花香味﹌/ 2023年08月17日 15:48/ 0 赞/ 28 阅读

相关 Ural 1078 segement

O(n^2)的动态规划的算法。 include <cstdio> include <cstring> include <cstdlib> in

爱被打了一巴掌/ 2022年08月11日 06:29/ 0 赞/ 140 阅读

相关 URAL--1007 codewords

三种信息传递过程中可能出错的方式，让你恢复原来正确的信息。我用的是分类暴搜，用字符串模拟的，这里还是是可行的，不过debug快坑死了o(╯□╰)o...... 后面还有一

落日映苍穹つ/ 2022年08月11日 00:44/ 0 赞/ 168 阅读

相关 URAL——1005 stone pile

题意：给你n个石头（1<=n<=20），给出每个石头的重量w\[i\]( 1<=w\[ i \] <= 100000),均分为两堆，求出两堆最小的差距重量，并输出。

浅浅的花香味﹌/ 2022年08月10日 18:29/ 0 赞/ 6 阅读

相关 Stones（优先队列）

Stones Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Ot

小咪咪/ 2022年08月01日 11:22/ 0 赞/ 113 阅读

相关 hdu1005

//两种方法，本以为会时间超限超限，就用数组将结果储存起来，没想到不用优化，直接ac了，判的有点松 \include <iostream> using name

小灰灰/ 2022年06月16日 10:22/ 0 赞/ 160 阅读

相关 Stones（优先队列）

![Image 1][]![Image 1][] ![Image 1][] ![Image 1][][原题][Link 1] 题意：奇数石头扔出去，偶数石头

╰半橙微兮°/ 2022年06月12日 12:00/ 0 赞/ 145 阅读

相关 URAL - 1056(DFS)

问题描述: Background Computer net is created by consecutive computer plug-up to one that h

Dear 丶/ 2022年06月04日 05:15/ 0 赞/ 168 阅读

相关 1159A A pile of stones

A. A pile of stones time limit per test 1 second memory limit per test 256 megaby

布满荆棘的人生/ 2022年01月31日 04:43/ 0 赞/ 198 阅读

相关 URAL 1029

题目大意：M层N列的矩阵（各元素均为正整数），找出一个路径从第一层到达第M层，使得路径上的所有数的和是所有可达路径中最小的，每次上到下一层以后就不能再上去，依次输出路径上的各点

清疚/ 2021年12月14日 00:45/ 0 赞/ 233 阅读