/* Programming 1 --50 Unaccept*/

#include <stdio.h>

int N,M;

long rp,ans[10001]={0};

char c[100001]={'\0'};

int main()

{

scanf("%d %d",&N,&M);

for(int i=1;i<=N;i++)

for(int j=1;j<=M;j++)

{

scanf("%ld",&rp);

for(int k=M;k>=j;k--)

if(ans[k]<ans[k-j]+rp)

ans[k]=ans[k-j]+rp;

if(j==M) gets(c);

}

printf("%ld",ans[M]);

return 0;

}

/* Programming 2 --100 Accept*/

#include <stdio.h>

int N,M;

long rp[101][101]={0},ans[10001]={0};

char c[10001]={'\0'};

int main()

{

scanf("%d %d",&N,&M);

for(int i=1;i<=N;i++)

for(int j=1;j<=M;j++)

{

scanf("%ld",&rp[i][j]);

if(j==M) gets(c);

}

for(int i=1;i<=N;i++)

for(int j=M;j>=1;j--)

for(int k=1;k<=j;k++)

if(ans[j]<ans[j-k]+rp[i][k])

ans[j]=ans[j-k]+rp[i][k];

printf("%ld",ans[M]);

return 0;

}

而且第一个程序的错误结果总是比第二个大。

谁讲讲这个为什么。

第一个相应的应是：

对于第i本作业用时j时，得到的rp。此时，用M...j进行一次0/1背包。也即第一次用M去背包，第二次用M-1背包，第三次用M-2......一直到j。这时，产生的结果有可能大于实际结果。

第二个相应的应是：

对于第i本作业，用M时间进行0/1背包。说详细些就是：第一个是对work[i][j],用M...j对它进行一次0/1背包，第二个是对work[i],即第i本作业进行0/1背包。

两者略有区别，所以产生的结果也会有误差。第一个结果会大些。

这个是我的理解，不知对与否。若高手有见解，不妨说出来听听，多谢！