Question

关于poj 1276题 提交后老是显示结果不对。但是使用它给的测试数据是对的，求大神指点

#include<stdio.h>
int p[11],nums[11];
int dp[11][10001];
int main()
{
int total,num;
scanf("%d %d",&total,&num);
for(int i=1;i<=num;i++)
scanf("%d %d",&nums[i],&p[i]);
for(int i=1;i<=num;i++)
for(int v=0;v<=total;v++)
{
int max=dp[i-1][v];
for(int j=1;j<=nums[i];j++)
{
if(v<j*p[i])
break;
else
{
if(max<dp[i-1][v-j*p[i]]+j*p[i])
max=dp[i-1][v-j*p[i]]+j*p[i];
}
}
dp[i][v]=max;
}
printf("%d\n",dp[num][total]);
}

Answer 1

#include<stdio.h>
#include<string.h>
#define num 100005
int hash[num];
int main()
{
//freopen("input.txt","r",stdin);
int cash,n,i,j,k;
int money_num[11],money[11];
while(scanf("%d%d",&cash,&n)!=EOF)
{
memset(hash,0,sizeof(hash));
for(i=0;i<n;i++)scanf("%d%d",&money_num[i],&money[i]);
hash[0]=1;
for(i=0;i<n;i++)
{
for(j=cash;j>=0;j--)
{
if(hash[j])
{
for(k=1;k<=money_num[i];k++)
{
if((j+k*money[i])>cash)break;
hash[j+k*money[i]]=1;
}
}
}
}
for(i=cash;i>=0;i--)
if(hash[i])
{
printf("%d\n",i);
break;
}
}
}