echo2001 @ 2019-11-20 13:10:57
//有依赖的背包问题
//金明的预算方案 NOIP 2006 提高组 第二题
//思路:转化为01背包问题.不过决策变为了1、不买这个主件;2、买这个主件,同时附件的购买还有四种情况
#include <iostream>
using namespace std;
int best[32000][240] = {0};
struct item_group
{
int main_v = 0;
int main_p = 0;
int main_vp = 0;
int surbordinate[3][3] = {0};
};
item_group group[61];
int maximum(int x, int y)
{
if (x > y)
return x;
return y;
}
int main()
{
int n = 0, m = 0;
cin >> n >> m;
int v = 0, p = 0, q = 0;
//input;
int num = 0;
for (int i = 1; i <= m; i++)
{
cin >> v >> p >> q;
if (q == 0)
{
num++;
group[num].main_p = p;
group[num].main_v = v;
group[num].main_vp = v * p;
}
else
{
if (group[q].surbordinate[1][0] == 0) //这是第一个附件
{
group[q].surbordinate[1][0] = v;
group[q].surbordinate[1][1] = p;
group[q].surbordinate[1][2] = v * p;
}
else //这是第二个附件
{
group[q].surbordinate[2][0] = v;
group[q].surbordinate[2][1] = p;
group[q].surbordinate[2][2] = v * p;
}
}
}
//开始dp
int temp = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= num; j++)
{
//决策有五种可能
best[i][j] = best[i][j - 1];
if (i - group[j].main_v >= 0)
{
temp = best[i - group[j].main_v][j - 1] + group[j].main_vp;
best[i][j] = maximum(best[i][j], temp);
}
if (i - group[j].main_v - group[j].surbordinate[1][0] >= 0)
{
temp = best[i - group[j].main_v - group[j].surbordinate[1][0]][j - 1] + group[j].main_vp + group[j].surbordinate[1][2];
best[i][j] = maximum(best[i][j], temp);
}
if (i - group[j].main_v - group[j].surbordinate[2][0] >= 0)
{
temp = best[i - group[j].main_v - group[j].surbordinate[2][0]][j - 1] + group[j].main_vp + group[j].surbordinate[2][2];
best[i][j] = maximum(best[i][j], temp);
}
if (i - group[j].main_v - group[j].surbordinate[1][0] - group[j].surbordinate[2][0] >= 0)
{
temp = best[i - group[j].main_v - group[j].surbordinate[1][0] - group[j].surbordinate[2][0]][j - 1] + group[j].main_vp + group[j].surbordinate[1][2] + group[j].surbordinate[2][2];
best[i][j] = maximum(best[i][j], temp);
}
}
}
cout << best[n][num] << endl;
return 0;
}