zd


私信TA

用户名:uq_55080596819

访问量:619

签 名:

等  级
排  名 998
经  验 2212
参赛次数 0
文章发表 7
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

TA的其他文章

挺好懂的, 因为有主件附件, 就把附件的加到主建就行了, 看作是一个。然后用01背包问题解法。

#include <bits/stdc++.h>
using namespace std;
const int N = 101010;

int n, m, sum = 1, sum2 = 1;
int a[N], a1[N];
int w, v, f[N], p;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> w >> v >> p;
		int qq = 0;
		qq = w * v;//乘上价值
		if (!p) {
			a1[sum2++] = w;
			a[sum++] = qq;
		} 
		else{
			a[p] += qq;
			a1[p] += w;
		}
	}
	sum -= 1;
	for (int i = 1; i <= sum; i++){
		for (int j = n; j >= a1[i]; j--){
			f[j] = max(f[j], f[j - a1[i]] + a[i]) ;
		}
	}
	cout << f[n] <<endl;
	return 0;
}


 

0.0分

0 人评分

  评论区