C 语言 购物单问题
购物单
http://www.nowcoder.com/questionTerminal/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; }