题解 | #购物单#
购物单
http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
//转化为背包问题
#include <stdio.h>
int main(){
int N,m; //总钱数、希望购买物品的个数
int v,p,q; //v物品价格、p物品重要程度、q=0为主件 q>0为某主件的附件，q值就是主件的编号
/*1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
五个物品，默认每个买一件。要求买附件必须买主件，买主件不必要买附件
第一个物品有四种组合方式：800、800+400、800+300、800+400+300
后两个物品没有附件，不考虑主附件限制。*/
int gv[61][4]; //定义 vq 数组来反应物品（主附组合）价格
int gw[61][4]; //定义 vp 数组来表示物品（主附组合）价值（价格 * 重要度）
int dp[3200] = {0}; //表示放入背包内的现有物品的总价值
//对附件进行主件二维数组的排列存储
scanf("%d%d",&N,&m);
for(int i = 1; i <= m; i++){
scanf("%d%d%d",&v,&p,&q);
if(q == 0){ //存为主件
gv[i][0] = v / 10;
gw[i][0] = v * p / 10;
}
else{ //大于 0 的存为对应附件（要求：输入时附件就跟在对应主件后面）
if(gv[q][1]){ //如果有第一个附件，就存为第二个附件
gv[q][2] = v / 10;
gw[q][2] = v * p / 10;
}else{ //如果没有第一附件就存为第一附件
gv[q][1] = v / 10;
gw[q][1] = v * p / 10;
}
}
}
//主附件组合（不在读取时组合是因为数据可能是附件在前主件在后）
for(int i = 1; i <= m; i++){
//主件 + 第一附件
gv[i][1] += gv[i][0];
gw[i][1] += gw[i][0];
//主件 + 第二附件
gv[i][2] += gv[i][0];
gw[i][2] += gw[i][0];
//主件 + 第一附件 + 第二附件
gv[i][3] = gv[i][1] + gv[i][2] - gv[i][0] ;
gw[i][3] = gw[i][1] + gw[i][2] - gw[i][0];
}
//状态方程：f(m,N) = dp[i][j] = max(dp[i][j],dp[i-1][j-gv[i][k]] + gw[i][k])
for(int i = 1; i <= m; i++){
for(int j = N/10; j > 0; j--){
//dp[i][j] = dp[i-1][j]; //什么都不买，即不买该主件（只买附件不合题意排除）
for(int k = 0; k <= 3; k++){
//（0）主件
//（1）主件 + 附件1
//（2）主件 + 附件2
//（3）主件 + 附件1 + 附件2
int tmp = dp[j - gv[i][k]] + gw[i][k];
if(gv[i][k] <= j && dp[j] < tmp){
dp[j] = tmp;
}
}
}
}
printf("%d",dp[N/10] * 10);
return 0;
}
无
无
