分石头

[编程题]分石头

热度指数：407 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

已知石头重量数组。将石头分为质量最接近的两组

输入描述:

数组，值为每个石头的质量

输出描述:

两组的质量（降序排序）

示例1

输入

5,1,1,1,1,1

输出

5,5

备注:

质量限定为 Integer

算法知识视频讲解

wise

两组最接近的情况为平分，那么我们可以理解成，如何将和的一半填的最满的问题，算是一个0-1背包问题吧。

   importjava.util.*;  
      
   publicclassMain{  
          
       publicstaticvoidmain(String[] args)  
       {  
           Scanner scanner = newScanner(System.in);  
           while(scanner.hasNext())  
           {  
               String input = scanner.next();  
               String[] A = input.split(",");  
               intn = A.length;  
               if(n <= 1)  
               {  
                   System.out.println(input + ",0");  
               }else{  
                   int[] arr = newint[n];  
                   intsum = 0;  
                   for(inti = 0; i < n ; i++)  
                   {  
                       arr[i] = Integer.valueOf(A[i]);  
                       sum += arr[i];  
                   }  
                   inthalf = sum / 2;  
                   int[] dp = newint[half + 1];  
                   intmax = Integer.MIN_VALUE;  
                   for(inti = 0; i < n ; i++)  
                   {  
                       for(intj = half ; j >= arr[i] ; j--)  
                       {  
                           dp[j] = dp[j - arr[i]] + arr[i];  
                           max = Math.max(max , dp[j]);  
                       }  
                   }  
                   System.out.println(sum - max + ","+ max);  
                   }  
           }  
       }  
   }  

发表于 2018-07-14 14:04:41 回复(1)

xxxxxxxxxxxxxxxa

/*
转化为01背包问题，背包体积为10，每个石头的价值为自身的重量，
1. F[i,v]表示背包恰好为v下，前i件物品的最大价值
2. F[i,v]=max{F[i-1,v],F[i-1,v-1]+Ci}
3. 注意非装满问题 F[0,0..N]=0 F[0..N,0]=0
4. 扫描数组，找到F[N,v]中最接近sum{Ci}/2的那个
*/

#include<iostream>
#include<vector>
using namespace std;
vector<int> stone_divide(vector<int> & nums){
    vector<int> F(nums.size()+1,0);
    for(int i=1;i<nums.size()+1;++i)
        for(int v=nums.size()+1;v>0;--v)
            F[v]=max(F[v],F[v-1]+nums[i-1]);
    int k=0,sum=0,tmp=9999;
    for(int i=0;i<nums.size();++i)
        sum+=nums[i];
    for(int i=0;i<F.size();++i){
        if(tmp>abs(F[i]-sum/2)){
            tmp=abs(F[i]-sum/2);
            k=i;
        }
    }
    if(F[k]>sum/2)
        return {F[k],sum-F[k]};
    return {sum-F[k],F[k]};
}


int main(void){
    vector<int> nums;
    int tmp;
    char comma;
    while(cin>>tmp){
        nums.push_back(tmp);
        cin>>comma;
    }
    nums=stone_divide(nums);
    cout<<nums[0]<<","<<nums[1]<<endl;  
}

当然该方法是有问题的，但在本题的测试用例中，却可以通过。

编辑于 2018-07-22 14:38:58 回复(0)

南屏机修组扛把子

官方的解析怎么是直接分段截开啊？？？

发表于 2022-11-30 10:07:58 回复(0)

terasum

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int main(int argc, char** argv){
    vector<int> vec;
    int num;
    while(true){
        scanf("%d",&num);
        vec.push_back(num);
        int r = scanf(",");
        if (r == EOF){
            break;
        }
    }
    int sum = 0, a = 0, b = 0;
    int i = 0, j = vec.size() - 1;
    while(i < j && i < vec.size() && j > 0){
        if (a <= b){
            a += vec[i];
            i++;
        }else{
            b += vec[j];
            j--;
        }
    }
    if(a >= b){
        cout<<a<<","<<b<<endl;
    }else{
        cout<<b<<","<<a<<endl;
    }


}

编辑于 2018-07-21 23:23:45 回复(0)

笨狗欢乐跳

int main()
{  vector<int>temp;  string str = "";  cin >> str;  for (auto i : str)  {  if (isdigit(i))  temp.push_back(i - '0');  }
    sort(temp.begin(), temp.end());
    vector<int>::iterator begin = temp.begin();
    vector<int>::iterator end = temp.end();
    vector<int>::iterator mid= temp.begin();
    int min = 100000;
    int half = 0, otherhalf = 0;
    while(mid!=end)
    {
        int init = 0;
        int init1 = 0;
        int x = accumulate(begin, mid+1,init);  int y= accumulate(mid+1, end, init1);
        if (abs(x - y) < min)
        {
            min = abs(x - y);
            half = x;
            otherhalf = y;
        }
        ++mid;
    }
    if (half > otherhalf)
        cout << half << "," << otherhalf;
    else
        cout << otherhalf << "," << half;
    return 0;
}

编辑于 2018-07-17 21:43:06 回复(0)

猪猪侠201806261909689

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void recur(string str, vector<string> &res, string &tmp, int start);
void main() {
      string str="abc";
      //cin >> str;
      //cout << str;
      //printf("%s", str);
        vector<string> res;
        //vector<string>::iterator i;

        string tmp = "";
        recur(str, res, tmp, 0);
        for (auto i = 0; i < res.size(); i++){
            //string s1 = res[i]+"/0";
            cout << res[i]<<endl;
        }
        system("pause");

    }
void recur(string str, vector<string> &res, string &tmp, int start){
    if (start == str.size()){
        res.push_back(tmp);
        return;
    }

    //cout << start;
    for (int i = start; i<str.size(); i++){
        //判断要交换的字符是否相同，相同就不用交换直接跳过（除了start位置与自己交换的情况）
        if (i != start&&str[start] == str[i])
            continue;
        if (str[start] != str[i]){
            cout << start;
        }
        swap(str[start], str[i]);
        tmp += str[start];
        recur(str, res, tmp, start + 1);

        tmp.pop_back();
    }

    }

发表于 2018-07-17 08:47:41 回复(0)