先写上二维方程的解决办法

时间:2019-09-29 07:48来源:快三平台下载编程
这是一道简单的动态规划题目,写出了转移方程就好办了。先写上二维方程的解决办法。 至于在HDU的OnlineJudge上有一组非常变态的数据。(骨头空间有可能为0,但价值不为零)。所以

这是一道简单的动态规划题目,写出了转移方程就好办了。先写上二维方程的解决办法。

至于在HDU的Online Judge上有一组非常变态的数据。(骨头空间有可能为0,但价值不为零)。所以weight循环必须从0开始。否则就是WA了。

该组变态测试数据如下:
1
2 0
20 1
0 1

答案是: 20

 1 #include<stdio.h> 2 #define M 1002 3 int max[M][M]; 4 int weight[M],value[M]; 5 int n,v; 6  7 void dp() 8 { 9     scanf("%d%d",&n,&v);10     int i,j;11     for(i=1;i<=n;i++)12     scanf("%d",&value[i]);13     for(i=1;i<=n;i++)14     scanf("%d",&weight[i]);15     for(i=1;i<=n;i++)16     for(j=0;j<=v;j++)                     //每次的v是单独针对这个物体而言的;17     {18     if(weight[i]<=j&&max[i-1][j-weight[i]]+value[i]>max[i-1][j])max[i][j]=max[i-1][j-weight[i]]+value[i];19     else max[i][j]=max[i-1][j];          20     }21     printf("%dn",max[n][v]);22 23 }24 25 26 int main()27 {28 int num;29 scanf("%d",&num);30 while(num--)31 dp();32 }

编辑:快三平台下载编程 本文来源:先写上二维方程的解决办法

关键词: