给出 N件物品并选出 M 件物品求解

给出 N件物品并选出 M 件物品

每件物品有三个属性a b c，选出的 M件物品的属性a 相加的后的绝对值suma，属性 b 相加的后的绝对值 sumb，属性c 相加的后的绝对值sumc 。使suma+sumb+sumc最大。

数据范围
0<M<N<10^5
-10^5<a、b、c<10^5

输入格式
N M
a1 b1 c1
a2 b2 c2
an bn cn
输出格式
打印一个整数表示最大值

输入输出样例
输入#1

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15
输出#1

这个问题可以使用贪心算法（Greedy Algorithm）来解决。具体步骤如下：

定义一个结构体Item来表示每件物品的属性，包括 a，b和c三个属性。
从N件物品中选择M件物品，可以采用组合（Combination）来实现，即枚举所有的M件物品的组合情况，并依次计算它们的属性总和。在遍历过程中，记录目前为止属性总和最大的组合及其对应的总和值。
最后得到的组合与总和即为问题的解。

以下是一个可能的C语言实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int a;
    int b;
    int c;
} Item;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    Item *items = (Item *)malloc(n * sizeof(Item));
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &(items[i].a), &(items[i].b), &(items[i].c));
    }
      
    int max_sum = 0;
    Item *max_items, *cur_items;
    max_items = (Item *)malloc(m * sizeof(Item));
    cur_items = (Item *)malloc(m * sizeof(Item));

    // 枚举所有的 M 件物品的组合情况
    for (int i = 0; i <= n - m; i++) {
        for (int j = i + 1; j <= n - m + 1; j++) {
            for (int k = j + 1; k <= n - m + 2; k++) {
                int sum_a = 0, sum_b = 0, sum_c = 0;
                for (int l = 0; l < m; l++) {
                    cur_items[l] = items[i+l];
                    sum_a += items[i+l].a;
                    sum_b += items[i+l].b;
                    sum_c += items[i+l].c;
                }
                int total_sum = abs(sum_a) + abs(sum_b) + abs(sum_c);
                
                // 更新最大值
                if (total_sum > max_sum) {
                    max_sum = total_sum;
                    for (int l = 0; l < m; l++) {
                        max_items[l] = cur_items[l];
                    }
                }
            }
        }
    }

    printf("Selected items:\n");
    for (int i = 0; i < m; i++) {
        printf("item%d: a=%d, b=%d, c=%d\n", i+1, max_items[i].a, max_items[i].b, max_items[i].c);
    }
    printf("sum(a)=%d, sum(b)=%d, sum(c)=%d, total=%d\n", 
           sum_a, sum_b, sum_c, max_sum);
    
    free(items);
    free(max_items);
    free(cur_items);

    return 0;
}

上述代码中，我们使用了三重循环来枚举所有的组合情况。在循环过程中，我们用 cur_items 和 max_items 分别记录当前处理的组合和目前为止属性总和最大的组合。每次计算完一组组合的属性总和后，就和当前最大值进行比较，如果比它更大，则更新最大值及其对应的组合。最后输出选中的物品及其属性总和。注意，这个算法的时间复杂度为 $O(n^3m)$，在 n 和 m 都很大时可能会超时。如果需要进一步优化可以考虑动态规划等算法。

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int seed=233;
const int N=4e4+10;

int w[100],v[100],dp[N];
vector<int>vec[100];
vector<pair<int,int>>thi[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i=1;i<=m;i++){
        int fa;
        scanf("%d%d%d",&w[i],&v[i],&fa);
        v[i]*=w[i];
        vec[fa].push_back(i);
        if(!fa)
            thi[i].pb(make_pair(w[i],v[i]));
    }
    for(int i=1;i<=m;i++){
        if(!vec[i].size()) continue;
        for(int j=0;j<vec[i].size();j++){
            thi[i].pb(make_pair(w[vec[i][j]]+w[i],v[vec[i][j]]+v[i]));
            for(int k=j+1;k<vec[i].size();k++)
                thi[i].pb(make_pair(w[vec[i][j]]+w[vec[i][k]]+w[i],v[vec[i][j]]+v[vec[i][k]]+v[i]));
        }
    }
    for(int i=1;i<=m;i++){
        if(!thi[i].size()) continue;
        for(int j=n;j>=0;j--){
            for(int k=0;k<thi[i].size();k++){
                if(j>=thi[i][k].first)
                    dp[j]=max(dp[j],dp[j-thi[i][k].first]+thi[i][k].second);
            }
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}

给出 N件物品并选出 M 件物品 求解

给出 N件物品并选出 M 件物品求解