- 金明的预算方案
- 2013-07-27 09:57:55 @
我的算法哪里有问题?现在在10组测试数据中只能通过4组
#include<iostream>
#include<cstring>
using namespace std;
int dp[61][3201];//动归的计算数组
int v[61][4]; //保存物品价格,其中,主件为0,(假如有的话)主件+附件1为1,主件+附件2为2,主件+附件1+附件2为3
int w[61][4]; //保存物品重要度*价格,因为重要度在后文中用处不大,因此在读入时就乘起来
int p[61]; //保存主件号
int is[61];//保存主件的样式(即0附件(1),1个附件(2),另一个附件(3),2个附件(4))数量
int main() {
int n,m;
cin >> n >> m;
n /= 10;
memset(is,0,sizeof(is));
for (int i=1;i<=m;i++){
cin >> v[i][0] >> w[i][0] >> p[i];
v[i][0] /= 10;
w[i][0] *= v[i][0];
if( !p[i]) is[i]++;//先把主件赋为1,附件为0
}
for (int i=1;i<=m;i++){
if( !is[i]){
v[p[i]][is[p[i]]] = v[i][0];//is[p[i]]的意思是物品i的主件的数量(也可以作为下一个样式的插入点)
w[p[i]][is[p[i]]] = w[i][0];
is[p[i]]++;//主件有附件,再加一
}
}
for (int i=1;i<=m;i++){
if( is[i]){
for (int j=1;j!=is[i];j++){
v[i][j] += v[i][0];
w[i][j] += w[i][0];
}
}
if( is[i] == 3){
v[i][3] = v[i][1]+v[i][2]-v[i][0];//这里主件会重复计算,因此减去一个
w[i][3] = w[i][1]+w[i][2]-w[i][0];
is[i]++;//再多一个样式
}
}
memset(dp,0,sizeof(dp));
int last = 0;
for (int i=1;i<=m;i++){
if( is[i]){
for (int j=1;j<=n;j++){
dp[i][j] = dp[last][j];
for (int k=0;k!=is[i];k++){
if( j>=v[i][k]) dp[i][j] = max(dp[last][j-v[i][k]] + w[i][k],dp[i][j]);
}
dp[0][0] = max(dp[i][j],dp[0][0]);
}
last = i;
}
}
cout << dp[0][0] * 10;
return 0;
}