题解 | #购物单#
购物单
http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int main(void)
{
int N,m; // N：钱，M总物品数
scanf("%d %d",&N,&m);
int x,y,z;
int value[m][4];// 价钱与重要度乘积
int cost[m][4];// 价钱，0：主；1、2：附
memset(value, 0, m * 4 * sizeof(int));
memset(cost, 0, m * 4 * sizeof(int));
for(int i=0;i<m;i++){
scanf("%d %d %d", &x, &y, &z);
// 分主附件，转化01背包问题
// 计算四种情况的value和cost
if(z==0){
value[i][0]=x*y;
cost[i][0]=x;
}
else if(cost[z-1][1]==0){
// 第z件为其主件，对应下标z-1
cost[z-1][1]=x;
value[z-1][1]+=x*y;
}
else{
cost[z-1][2]=x;
value[z-1][2]=x*y;
cost[z-1][3] = cost[z-1][1]+cost[z-1][2];
value[z-1][3] = value[z-1][1]+value[z-1][2];
}
}
for(int i=0;i<m;i++){
for(int k=1; k<4;k++){
cost[i][k] += cost[i][0];
value[i][k] += value[i][0];
}
}
// for(int i=0; i<m; i++){
// for(int k=0;k<4;k++)
// printf("%d %d ", cost[i][k], value[i][k]);
// printf("\n");
// }
int dp[m+1][N+1];
int max_v=0;
memset(dp, 0, (m+1)*(N+1)*sizeof(int));
// 可以考虑优化，0行略过
for(int i=1; i<=m; i++){
for(int j=10;j<=N;j+=10){
max_v = dp[i-1][j];
for(int k=0;k<4;k++){
if(k>0 && cost[i-1][k]==cost[i-1][0])
break;
if(j-cost[i-1][k]>=0)
max_v = max(max_v,dp[i-1][j-cost[i-1][k]]+value[i-1][k]);
}
dp[i][j] = max_v;
}
}
printf("%d", dp[m][N]);
return 0;
}
