- 金明的预算方案
- 2017-08-18 14:46:30 @
话说Pascal是可以过的,翻译一下就…… 不知所措~~
```c++
#include <iostream>//输入输出
#include <climits>
#include <cstring>
using namespace std;
const int maxn = LONG_MAX / 2;
struct data{
int x,y;
};
data f[61][3];
int k[320001];
int main()
{
int m,n;
cin >> m >> n;
for (int i = 1; i <=n; i++)
{
int a,b,c;
cin >> a >> b >> c;
if (c == 0)
{
f[i][0].x=a;
f[i][0].y=a*b;
} else
{
if (f[c][1].y==0)
{
f[c][1].x=a;
f[c][1].y=a*b;
} else
{
f[c][2].x=a;
f[c][2].y=a*b;
}
}
}//f[i]为编号,[0]主件 [1]附件1 [2] 附件2
memset(k, 0, sizeof(k));
for (int i=1; i<=n; i++)
{
if (f[i][0].y==0) continue;
for (int j=m; j>=0; j--)
{
if (j+f[i][0].x<=m)
if (k[j]+f[i][0].y>k[j+f[i][0].x])
k[j+f[i][0].x]=k[j]+f[i][0].y;
if (j+f[i][0].x+f[i][1].x<=m)
if (k[j]+f[i][0].y+f[i][1].y>k[j+f[i][0].x+f[i][1].x])
k[j+f[i][0].x+f[i][1].x]=k[j]+f[i][0].y+f[i][1].y;
if (j+f[i][0].x+f[i][2].x<=m)
if (k[j]+f[i][0].y+f[i][2].y>k[j+f[i][0].x+f[i][2].x])
k[j+f[i][0].x+f[i][2].x]=k[j]+f[i][0].y+f[i][2].y;
if (j+f[i][0].x+f[i][1].x+f[i][2].x<=m)
if (k[j]+f[i][0].y+f[i][1].y+f[i][2].y>k[j+f[i][0].x+f[i][1].x+f[i][2].x])
k[j+f[i][0].x+f[i][1].x+f[i][2].x]=k[j]+f[i][0].y+f[i][1].y+f[i][2].y;
}
}//不标准的01背包 k[i]花i元可达到的最大收益
cout << k[m] << endl;
return 0;
}
1 条评论
-
孖作多情、 LV 9 @ 2017-08-18 14:51:15
顺便庆祝第一次在讨论界面成功打出代码,而不是“居左”!!
- 1