首页 > 试题广场 >

石头碰撞

[编程题]石头碰撞

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

给定一组石头，每个石头有一个正数的重量。每一轮开始的时候，选择两个石头一起碰撞，假定两个石头的重量为x，y，x<=y,碰撞结果为
1. 如果x==y，碰撞结果为两个石头消失
2. 如果x != y，碰撞结果两个石头消失，生成一个新的石头，新石头重量为y-x

最终最多剩下一个石头为结束。求解最小的剩余石头质量的可能性是多少。

输入描述:

第一行输入石头个数(<=100)

第二行输入石头质量，以空格分割，石头质量总和<=10000

输出描述:

最终的石头质量

示例1

输入

6
2 7 4 1 8 1

输出

算法知识视频讲解

pmad

简单说下思路，利用0-1背包方法求出能将石头合并成2堆的情况，dp[j]代表是否能将石头分成其中一堆为j，另一堆为(sum-j)，其中一堆的最小值肯定不超过总和的一半，最后最接近的两堆即为最小值

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt(),sum=0,result=0;
        int[] nums=new int[n+1];
        for(int i=1;i<=n;i++) {
            nums[i]=scanner.nextInt();
            sum+=nums[i];
        }
        boolean[] dp=new boolean[sum/2+1];
        dp[0]=true;
        for(int i=1;i<=n;i++)
            for(int j=sum/2;j>=nums[i];j--)
                dp[j]|=dp[j-nums[i]];
            
        for(int j=sum/2;j>=0;j--)
            if(dp[j]) {
               result=Math.abs(j-(sum-j));
               break;
            }
        System.out.println(result);
    }
}

编辑于 2020-03-16 11:23:34 回复(5)

快手校招实习社招内推

转换为0-1背包问题

#include <iostream>
(720)#include <vector>
#include <algorithm>
using namespace std;
 
class Solution
{
    public:
        int test(int n, vector<int> weights)
        {
            int sum = 0;
            for (int weight:weights)
            {
                sum+=weight;
            }
            int maxCapcity = sum/2;
            vector<int> dp(maxCapcity+1,0);
            for (int i=0;i<n;i++)
            {
                for (int j=maxCapcity;j>=weights[i];j--)
                {
                    dp[j] = max(dp[j],dp[j-weights[i]]+weights[i]);
                }
            }
            return sum - 2*dp[maxCapcity];
        }
};
 
int main()
{
    int n;
    cin >> n;
    vector<int> weights(n);
    for (int i=0;i<n;i++)
    {
        cin >> weights[i];
    }
    int res = Solution().test(n,weights);
    cout << res;
    return 0;
}

发表于 2020-03-21 18:02:59 回复(3)

远征的梦想

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int rockNum = Integer.parseInt(sc.nextLine());
        int[] rockWeights = new int[rockNum];
        String[] strs = sc.nextLine().split(" ");
        int sumWeight = 0;
        for (int i = 0; i < rockNum; i++) {
            rockWeights[i] = Integer.parseInt(strs[i]);
            sumWeight += rockWeights[i];
        }

        int[] dp = new int[(sumWeight / 2) + 1];
        for (int rockWeight : rockWeights) {
            for (int i = sumWeight / 2; i >= rockWeight; i--) {
                dp[i] = Math.max(dp[i], dp[i - rockWeight] + rockWeight);
            }
        }
        System.out.println(sumWeight - 2 * dp[sumWeight / 2]);
    }

}

发表于 2020-04-11 16:15:47 回复(0)

C/C++

爱吃福鼎肉片的狼人

01背包问题

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
    int num;
    cin >> num;
    int *storn = new int[num];
    for(int i = 0; i < num; i++) cin >> storn[i];

    int sum = 0;
    for(int i = 0; i < num; i++) sum += storn[i];
    int max_weight = sum / 2;
    int *weight = new int[max_weight + 1];
    
    for(int i = 0; i < num; i++){
        for(int j = max_weight; j >= storn[i]; j--){
            weight[j] = max(weight[j], weight[j - storn[i]] + storn[i]);
        }
    }
    cout << sum - 2 * weight[max_weight];
    return 0;
}

发表于 2022-04-07 17:45:50 回复(0)

奶茶妹夫

package 快手2020校园招聘秋招笔试工程C试卷;

import java.util.Scanner;

/**
 * Project: 100%
 * Author : en_zhao
 * Email  : 
 * Date   : 2020/8/3
 */
public class Main002 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //每个物品的重量
        int num[] = new int[n+1];
        int s = 0;
        //求总数
        for(int i = 0;i < n;i++){
            num[i] = sc.nextInt();
            s += num[i];
        }

        //背包的重量
        int W = s / 2;
        //背包最优解 java默认初始化为0
        int[] dp = new int[W + 1];
        for(int i = 0; i < n;i++){
            for(int j = W; j-num[i] >= 0 ;j--){
                dp[j] = Math.max(dp[j], dp[j-num[i]]+num[i]);
            }
        }
        System.out.println(s - dp[W] - dp[W]);
    }
}

发表于 2020-08-03 20:08:55 回复(0)

Cyan1956

参考了pmad的答案写的。

我们可以考虑以下过程：

把石头分为两堆，从A堆中取出一块石头m，B堆中取出n，不妨设m>=n。
碰撞后碎片为m-n，应放入A堆。
对比碰撞前后，你会发现两个堆的质量之差没有发生变化。并且重复碰撞下去直到只剩一堆的时候，你会发现剩下的质量就是两堆之差。真的是非常的巧妙，所以为了使最终剩余的质量最小，我们应该让两堆石头的质量尽可能接近，也就是尽量平均。
另外，这里的内层for很巧妙。我最开始写的是i++，这样会导致v的重复利用。比如v是一块20的石头，那么20,40,60...都会被标记为true。采用递减循环就可以避免这个问题。

package main

import (
    "fmt"
)

func main() {
    var n, tmp, sum, max int
    var w []int
    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        fmt.Scan(&tmp)
        sum += tmp
        w = append(w, tmp)
    }
    flag := make([]bool, sum/2+1)
    flag[0] = true
    for _, v := range w {
        for i := sum / 2; i >= v; i-- {
            flag[i] = flag[i] || flag[i-v]
        }
    }
    for i := sum / 2; i >= 0; i-- {
        if flag[i] {
            fmt.Print(sum - 2*i)
            break
        }
    }
}

我开始维护CSDN了，来点个赞呗~

编辑于 2020-04-05 21:06:02 回复(1)

牛客178546404号

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            sum += nums[i];
        }
        int[][] dp = new int[n + 1][sum / 2 + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum / 2; j++) {
                 if (j >= nums[i - 1]) {
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
                 } else {
                     dp[i][j] = dp[i - 1][j];
                 }
            }
        }
        System.out.print(sum - 2 * dp[n][sum / 2]);
    }
}

发表于 2021-10-25 19:27:51 回复(0)

Soccer,soccer,soccer!

import java.util.Scanner;
/*
问题：石头碰撞，给定一组石头，碰撞之后产生碎片为两者之差，求最后只剩下一个石头的最小质量。n<=100,质量总和<=10000
思路：每次都选最大的两个相碰，产生的差值加入list重新排序。没有经过证明
后来的算例证明是错误的
题解：动态规划，01背包问题
首先是转换，巧妙！
将石头分成两堆，这两堆的质量之差，相当于碰撞到最后仅剩的一个石头的重量。所以关键在于分成两堆质量相差最近的
假设总质量为sum，其中一堆一定不超过sum/2，设背包质量为sum/2，问题转化为一组石头如何能尽量装满背包。动态规划
对于数组nums[n+1]，nums[1]~nums[n]代表1~n号石头的质量。设dp[i][j]代表背包容量剩余j，考虑前i个石头(1~i)，能装的最大质量。
1.j<nums[i], 不装i，dp[i][j]=dp[i-1][j]
2.j>=nums[i]
    1) 装i，dp[i][j]=dp[i-1][j-nums[i]]+nums[i]
    2) 不装i，dp[i][j]=dp[i-1][j]
    即dp[i][j]=max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
最终要求的是dp[n][sum/2]，和sum-前者的差值，就是答案。
空间优化：对于i轴从上到下，j轴从左到右的填表（相当于数组的行和列），是从上到下从左到右一行行填表的，
每一行仅由上一行决定。
所以dp[][]可以优化为一维。
*/
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] nums=new int[n+1];
        int sum=0;
        for(int i=1;i<=n;i++) {
            nums[i]=sc.nextInt();
            sum+=nums[i];
        }
        int[][] dp=new int[n+1][sum/2+1]; //dp[0][..]和dp[..][0]默认为0,边界条件解决
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum/2;j++){
                if(j<nums[i]) dp[i][j]=dp[i-1][j];
                else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
            }
        }
        int ans=(sum-dp[n][sum/2])-dp[n][sum/2]; //dp[n][sum/2]是以sum/2为背包容量，能装的最大质量
        System.out.println(ans);
    }
}

发表于 2020-11-05 11:58:49 回复(0)

风祈

import java.util.*;

/**
 * @Author: 
 * @Date: 2020/7/26 19:48
 * <p>
 * 功能描述:
 */
public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[] stones = new int[n] ;
        for(int i = 0; i < n;i++){
            stones[i] = sc.nextInt();
        }
        int ans = lastStoneWeightII(stones);
        System.out.println(ans);
    }


    public static int lastStoneWeightII(int[] stones) {
        /*
         1.换一种想法，就是将这些数字分成两拨，使得他们的和的差最小
         2.因此可以简单地把所有石头看作两堆,假设总重量为 sum,
         则问题转化为背包问题：如何使两堆石头总重量接近 sum / 2
         3.两堆石头的价值(重量)都只能接近
         */
        int len = stones.length;
        /* 获取石头总重量 */
        int totalStone = 0;
        for (int i : stones) {
            totalStone += i;
        }

        int maxCapacity = totalStone / 2;
        /*
         1.这个是0-1背包的dp定义，dp[i][w]:  前i个商品，当容量为w时，最大价值为dp[i][w]
         2.对照一下此题dp数组定义，dp[i][j]: 前i个石头，当容量为j时，最大重量为dp[i][j]
        */
        int[][] dp = new int[len + 1][totalStone + 1];


        for (int i = 1; i < len + 1; i++) {
            for (int j = 1; j < maxCapacity + 1; j++) {
                if (j - stones[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - stones[i - 1]] + stones[i - 1], dp[i - 1][j]);
                }
            }
        }
        return totalStone - 2 * dp[len][maxCapacity];

    }
}

发表于 2020-07-26 20:12:53 回复(0)

楠楠呀

//0-1背包，昨天有一个类似的三层背包 和这个非常类似 都快给我搞混了，其实挺好理解的
//菜菜
#include<vector>
using namespace std;

class Solution{
  public:
    int getMin(vector<int> arr){
        int sum = 0;
        for(int i=0;i<arr.size();i++){
            sum +=arr[i];
        }
        int C = sum/2;
        vector<vector<int>> dp(arr.size(),vector<int>(C+1,0));
        for(int j=0;j<=C;j++){
            dp[0][j] = arr[0] <=j?arr[0]:0;
        }
        for(int i=1;i<arr.size();i++){
            for(int j=0;j<=C;j++){
                dp[i][j] = dp[i-1][j];
                if(arr[i] <= j){
                    dp[i][j] = max(dp[i][j],arr[i] + dp[i-1][j-arr[i]]);
                }
            }
        }
        return sum - dp[arr.size()-1][C] * 2;
        
    }
};

int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    Solution c1;
    cout<<c1.getMin(arr)<<endl;
    return 0;
}

发表于 2020-06-07 20:48:09 回复(0)

C/C++

字节跳动2022校招提前批内推

//dp求法
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n = 0 ;
    cin>>n;
    vector<int>nums;
    int tmp = 0;
    int sum = 0;
    while(cin>>tmp)
    {
        nums.push_back(tmp);
        sum+=tmp;
    }
    //dp
    int C = sum/2;
    vector<vector<int>>dp(n,vector<int>(C+1,0));
    for(int c = 0; c<=C ; ++c)
        dp[0][c] = nums[0]>c?0:nums[0];
    for(int i = 1 ; i < n ; ++i)
        for(int c = 0 ; c <=C ; ++c)
        {
            if(c>=nums[i])
                dp[i][c] = max(dp[i-1][c] , nums[i] + dp[i-1][c-nums[i]]);
            else
                dp[i][c] = dp[i-1][c];
        }
    cout<<sum - dp[n-1][C] * 2;
    return 0;
}

01背包问题，用递归方式解决，加上剪枝，避免了重复计算，时间效率还不错。

#include<iostream>
(720)#include<vector>
#include<cassert>
(4983)#include<algorithm>
using namespace std;

class Solution{
private:
	//物品价值列表v, 重量列表w，当前背包容量c ， 当前考虑的物品索引范围[0，index],返回此时能获得的最大价值
	vector<vector<int>>meno;
	int maxValue_recursion(const vector<int>&v, const vector<int>&w, int c, int index)
	{
		//终止条件
		if (c == 0 || index < 0)return 0;
		//递归过程
		if (meno[index][c] != -1)return meno[index][c];
		int res = maxValue_recursion(v, w, c, index - 1);
		if (c >= w[index])
			res = max(res, v[index]+maxValue_recursion(v, w, c - w[index], index - 1));
		meno[index][c] = res;
		return res;
	}
public:
	int maxValue(const vector<int>& v, const vector<int>& w, int C)
	{
		assert(v.size() == w.size());
		int n = v.size();
		meno = vector<vector<int>>(n,vector<int>(C+1,-1));
		return maxValue_recursion(v, w, C, n - 1);
	}
};
int main()
{
    int n = 0;
    cin>>n;
    vector<int>v;
    int tmp = 0;
    int sum = 0;
    while(cin>>tmp)
    {
        v.push_back(tmp);
        sum+=tmp;
    }

    Solution sl;
    int res = sum - sl.maxValue(v,v,sum/2)*2;
    cout<<res;

编辑于 2020-04-13 23:13:05 回复(0)

7778888

#include<iostream>

using namespace std;

const int N = 110;
const int M = 10010;
int a[N];
int f[N][M];

int main() {
    
    int n;
    scanf("%d", &n);
    int sum = 0;
    
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    int V = sum / 2;
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= V; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= a[i]) f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]);
        }
    }

    cout << (sum - f[n][V]) - f[n][V];
    
    return 0;
    
    
}

发表于 2020-04-06 00:08:59 回复(1)