题解 | 金明的预算-NOIP2006提高组复赛
金明的预算方案
https://ac.nowcoder.com/acm/contest/254/B
算法知识点: DP，分组背包问题
复杂度： )
解题思路：
可以将每个主件及其附件看作一个物品组，记主件为 ，两个附件为
,则最多一共有4种组合：
这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。
C++ 代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair <int, int> PII;
const int N = 70,
M = 32010;
int m, n;
PII a[N];
vector<PII> b[N];
int f[M];
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
int v, w, p;
scanf("%d%d%d", &v, &w, &p);
w *= v;
if (!p) a[i] = {
v, w
};
else b[p].push_back(
{
v, w
});
}
for (int i = 1; i <= n; i++)
{
if (!a[i].first) continue;
for (int j = m; j >= 0; j--)
for (int k = 0; k < 1 << b[i].size(); k++)
{
int v = a[i].first, w = a[i].second;
for (int u = 0; u < b[i].size(); u++)
if (k >> u &1)
{
v += b[i][u].first;
w += b[i][u].second;
}
if (j >= v) f[j] = max(f[j], f[j - v] + w);
}
}
printf("%d\n", f[m]);
return 0;
} 
小米集团工作强度 267人发布
投递小米集团等公司10个岗位 >