vlambda博客
学习文章列表

小王子看了一下地上的宝石，分别是1KG，3KG，5KG，7KG，10KG，价值（如图）

对于这道题，首先可能会想到暴力枚举，但是暴力方式计算量实在太大，有超时的风险。我们应该想一个简单快捷的办法，恶龙只要求我们说出最终能够实现的最大价值，而不需要实现最大价值的组合顺序。这么说来，就应该用动态规划解决问题。

为了清晰表述和理解，我们首先需要分配一个二维数组为a[N][M+1],如题所述为a[5][11],得到数组之后（初始化情况请看下图），我们开始在这个数组中填入数据，下面是分析过程

三、转移方程（核心）

A[i][V]=min{A[i-1][V],A[i-1][V-W]+P}

大括号里分两个部分，前面是如果不放入当前宝石所能产生的最大价值，后面相反。对于后者，我们可以这么理解：我们如果把这块宝石放进去，或多或少会有剩余空间（否则根本不必考虑），那么这剩余的空间所能够容纳的最高价值是多少呢？这个剩余空间肯定小于当前空间，对于这个剩余空间的最优解，我们之前已经计算过的，在此处：2号宝石质量为3，价值为4。当容量为3的时候，如果不放入2号宝石最大价值为a[1][3]，就是1。如果放入2号宝石，那么最大价值经过上述公式计算可以得出为A[2-1][3-3]+4=0+4=4,  则A[2][3]=4。

以此类推，可得第二列。

同时，我们可以计算出表格的全部内容

所以在题目要求下最高价值是20，解题完毕。小王子这就可以把公主领走啦！

下面是代码部分

四、代码实践（C语言）

#include<stdio.h>int max(int x,int y);int main(void){ int n,m,k,a[1000],b[100][2],i,j,shi,jia; printf("请输入背包容量：\n") ;  scanf("%d",&n); printf("请输入宝石个数：\n") ;  scanf("%d",&m);
 for(i=0;i<=n;i++) a[i]=0; printf("请逐个输入宝石的质量和价值：\n") ;  for(i=0;i<m;i++){
 scanf("%d%d",&shi,&jia); for(j=n;j>=shi;j--){ a[j]=max(a[j],a[j-shi]+jia); } }

printf("可以实现的宝石最大价值为%d",a[n]);
}int max(int x,int y){ if(x>y) return x; return y;}

近日以来防疫形势严峻，同学们应当停留家中尽量不要外出走动。勤通风，勤洗手，注意个人卫生，不要熬夜，早睡早起提高身体免疫力！祝大家身体健康，祝武汉早日渡过难关！

武汉加油!