这个题目直接悲剧了超时不知道多少次了，连二进制都用上了，这个不科学啊。今天突然理解到其实刚开始把所有的状态全部赋值为0，也就是这个状态是不可达的，当然dp[0]=1这个是初始化。然后后面按照背包直接来就好，以前的时候我们是这么写的（我已经用二进制做了，所以直接写了，具体操作看代码）dp[k]=max(dp[k],dp[k-w[i]]+v[i]);现在其实只要dp[k]==1我们就不用管，反之看一下dp[k-w[i]]的值，如果是0说明这个状态是不可达的，那么在当前的情况下必然dp[k]的值不可修改，最后的时候看一下有哪些值是1就可以了。擦，自己的想象力碉堡了。呵呵呵呵。
[cpp]
#include
#include
#include
#include
using namespace std;
int a[110],c[110];
int dp[100000];
vector
int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int n,m,p,ko,sum,k,i;
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
fuck.clear();
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&c[i]);
for(i=1;i<=n;i++)
{
for(p=1;p<=c[i];p=p*2)
{
ko=p*a[i];
fuck.push_back(ko);
c[i]=c[i]-p;
}
if(c[i]!=0)
fuck.push_back(c[i]*a[i]);
}
sum=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int j=0;j
if(dp[k-fuck[j]]==1)
dp[k]=1;
for(i=1;i<=m;i++)
if(dp[i]==1)
sum=sum+1;
cout<
return 0;
}
#include
#include
#include
#include
using namespace std;
int a[110],c[110];
int dp[100000];
vector
int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int n,m,p,ko,sum,k,i;
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
fuck.clear();
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&c[i]);
for(i=1;i<=n;i++)
{
for(p=1;p<=c[i];p=p*2)
{
ko=p*a[i];
fuck.push_back(ko);
c[i]=c[i]-p;
}
if(c[i]!=0)
fuck.push_back(c[i]*a[i]);
}
sum=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int j=0;j
if(dp[k-fuck[j]]==1)
dp[k]=1;
for(i=1;i<=m;i++)
if(dp[i]==1)
sum=sum+1;
cout<
return 0;
}