這個題目直接悲劇了超時不知道多少次了，連二進制都用上了，這個不科學啊。今天突然理解到其實剛開始把所有的狀態全部賦值為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]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<vector>
#include<cstring>
#include<stdio.h>
using namespace std;
int a[110],c[110];
int dp[100000];
vector<int> fuck;
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<fuck.size();j++)
for(k=m;k>=fuck[j];k--)
if(dp[k-fuck[j]]==1)
dp[k]=1;
for(i=1;i<=m;i++)
if(dp[i]==1)
sum=sum+1;
cout<<sum<<endl;
}
return 0;
}
</SPAN>
#include<iostream>
#include<vector>
#include<cstring>
#include<stdio.h>
using namespace std;
int a[110],c[110];
int dp[100000];
vector<int> fuck;
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<fuck.size();j++)
for(k=m;k>=fuck[j];k--)
if(dp[k-fuck[j]]==1)
dp[k]=1;
for(i=1;i<=m;i++)
if(dp[i]==1)
sum=sum+1;
cout<<sum<<endl;
}
return 0;
}
