信息可视化网站,新媒体口碑营销案例,别墅设计公司排名前十强,网络服务调查问卷P1757 通天之分组背包 题目背景 直达通天路小A历险记第二篇 题目描述 自01背包问世之后#xff0c;小A对此深感兴趣。一天#xff0c;小A去远游#xff0c;却发现他的背包不同于01背包#xff0c;他的物品大致可分为k组#xff0c;每组中的物品相互冲突#xff0c;现在小A对此深感兴趣。一天小A去远游却发现他的背包不同于01背包他的物品大致可分为k组每组中的物品相互冲突现在他想知道最大的利用价值是多少。 输入输出格式 输入格式两个数m,n表示一共有n件物品总重量为m 接下来n行每行3个数ai,bi,ci表示物品的重量利用价值所属组数 输出格式一个数最大的利用价值 输入输出样例 输入样例#1input 45 410 10 110 5 15 20 250 400 2 输出样例#1output:30 说明 1m1000 1n1000 组数t100 一直以为背包问题最后出结果要扫一遍f今天才发现直接输出f[容积]就够了。。 分组背包其实很简单每一个组看成一个物品就是一个01背包。 然后在每个组里选加进去之后得到的最大值就可以。 我用了vector存每个组其实完全可以用二维数组[i][0]来存个数。 最好别用vector尽管我用了容易被卡 #include iostream
#include cstdio
#include cstdlib
#include algorithm
#include cstring
#include vector
using namespace std;#define max(a,b) ((a) (b) ? (a) : (b))
#define min(a,b) ((a) (b) ? (a) : (b))inline int read()
{int x 0;char ch getchar();char c ch;while(ch 9 || ch 0)c ch,ch getchar();while(ch 9 ch 0)x x * 10 ch - 0,ch getchar();if(c -)return -1 * x;return x;
}const int INF 99999999999;int n,m,groupn;
vectorint group[100 10];
int f[1000 10];
int w[1000 10];
int v[1000 10];
int minn[100 10];int main()
{m read();n read();for(int i 1;i n;i ){int temp;v[i] read();w[i] read();temp read();group[temp].push_back(i);minn[temp] min(minn[temp], v[i]);groupn max(groupn, temp);}for(int i 1;i groupn;i ){int size group[i].size() - 1;for(int j m;j minn[i];j --){for(int k 0;k size;k ){if(j v[group[i][k]])f[j] max(f[j],f[j - v[group[i][k]]] w[group[i][k]]);}}}printf(%d, f[m]);return 0;
}转载于:https://www.cnblogs.com/huibixiaoxing/p/6734172.html
