XM9. 资产包打包
描述
在金融资产交易中，经常涉及到资产包的挑选打包。在资产包打包过程中，每种类型的资产有固定的数量与价值，需选择某几种资产打包，使得资产包总价值最大。打包时每种资产只能整体打包，不能分割。假设现有可容纳M条资产的资产包，另外有N种资产。资产Na数量为Ta条，总价值为Va元；资产Nb数量为Tb条，总价值为Vb元；资产Nc数量为Tc条，总价值为Vc元......；资产Nn数量为Tn，总价值为Vn。编写算法，挑选哪些类型资产放入资产包可使得资产包总价值最大？输入描述
资产总量,资产种类,每类资产条数,每类资产价值(逗号分隔)；其中每类资产条数与每类资产价值为空格分隔。输出描述
资产包中资产最大总价值示例1
输入:
12,3,4 5 7,500 600 800
输出:
1400
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-11-17
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct package
{
int num;
int value;
}pack,*Ppack; //模板，定义一个物体的数量和价值
int main()
{
int m,n,i,j;
scanf("%d,%d",&m,&n); //背包容量和资产种类
Ppack p=(Ppack)calloc(n,sizeof(pack)); //
int *dp=(int *)calloc(m+1,sizeof(int));
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].num);
//printf("%d\n",p[i].num);
} //输入每种资产的条数
}
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].value);
//printf("%d\n",p[i].value);
} //每种资产对应的价值
}
for(i=0;i<n;i++)
{
for(j=m;j>=p[i].num;j--)
{
dp[j]= dp[j] > (dp[j-p[i].num]+p[i].value)
? dp[j] : (dp[j-p[i].num]+p[i].value);
//printf("%d %d\n",j,dp[j]);
}
}
printf("%d\n",dp[m]);
free(dp);
free(p);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-07-22
#include <stdio.h>
#include <stdlib.h>
int max(int a,int b)
{
return a>b?a:b;
}
int main(void) {
int x,n,i=0,j;
scanf("%d,%d,",&x,&n);
int a[n],b[n],dp[10000];
memset(dp,0,sizeof(dp));
while(1)
{
scanf("%d",&a[i++]);
if(getchar()==',')
break;
}
for(i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
for(i=0;i<n;i++)
{
for(j=x;j>=a[i];j--)
{
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
// printf("dp[%d]=%d\t",j,dp[j]);
}
// printf("\n");
}
printf("%d",dp[x]);
// printf("x=%d,n=%d\n",x,n);
// for(int i=0;i<n;i++)
// {
// printf("a[%d]=%d,b[%d]=%d\n",i,a[i],i,b[i]);
// }
}
C 解法, 执行用时: 2ms, 内存消耗: 456KB, 提交时间: 2020-05-14
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct package
{
int num;
int value;
}pack,*Ppack;
int cmp(const void *a,const void *b)
{
Ppack aa=(Ppack)a;
Ppack bb=(Ppack)b;
if(aa->value==bb->value)
return (((aa->num)>(bb->num))?1:-1);
else return (((aa->value)>(bb->value))?1:-1);
}
int main()
{
int m,n,i,j;
scanf("%d,%d",&m,&n);
Ppack p=(Ppack)calloc(n,sizeof(pack));
int *dp=(int *)calloc(m+1,sizeof(int));
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].num);
//printf("%d\n",p[i].num);
}
}
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].value);
//printf("%d\n",p[i].value);
}
}
for(i=0;i<n;i++)
{
for(j=m;j>=p[i].num;j--)
{
dp[j]= dp[j] > (dp[j-p[i].num]+p[i].value)
? dp[j] : (dp[j-p[i].num]+p[i].value);
//printf("%d %d\n",j,dp[j]);
}
}
printf("%d\n",dp[m]);
free(dp);
free(p);
return 0;
}
C++14 解法, 执行用时: 2ms, 内存消耗: 488KB, 提交时间: 2020-05-17
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct package
{
int num;
int value;
}pack,*Ppack;
int cmp(const void *a,const void *b)
{
Ppack aa=(Ppack)a;
Ppack bb=(Ppack)b;
if(aa->value==bb->value)
return (((aa->num)>(bb->num))?1:-1);
else return (((aa->value)>(bb->value))?1:-1);
}
int main()
{
int m,n,i,j;
scanf("%d,%d",&m,&n);
Ppack p=(Ppack)calloc(n,sizeof(pack));
int *dp=(int *)calloc(m+1,sizeof(int));
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].num);
//printf("%d\n",p[i].num);
}
}
if(getchar()==',')
{
for(i=0;i<n;i++)
{
scanf("%d",&p[i].value);
//printf("%d\n",p[i].value);
}
}
for(i=0;i<n;i++)
{
for(j=m;j>=p[i].num;j--)
{
dp[j]= dp[j] > (dp[j-p[i].num]+p[i].value)
? dp[j] : (dp[j-p[i].num]+p[i].value);
//printf("%d %d\n",j,dp[j]);
}
}
printf("%d\n",dp[m]);
free(dp);
free(p);
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 320KB, 提交时间: 2021-08-30
#include<stdio.h>
int max_m(int a, int b)
{
return (a > b) ? a : b;
}
int M, n, tiaoshu[10000], value[10000], dp[10000];
int main()
{
int i, j, k;
while (scanf("%d,%d,", &M, &n) != EOF)
{
for (i = 1;i <= n;i++)
{
scanf("%d", tiaoshu + i);
}
getchar();
for (i = 1;i <= n;i++)
{
scanf("%d", value + i);
}
for (i = 0;i < 1000;i++)
dp[i]=0;
for (i = 1;i <= n;i++)
for (j=M;j>=tiaoshu[i];j--)
{
dp[j]=max_m(dp[j],dp[j-tiaoshu[i]]+value[i]);
}
printf("%d", dp[M]);
}
}