分析:
我们要记录的是这个状态能不能到达,而不是这个状态能装多少
dp[i] 表示当前物品,刚好装满i的背包能否达到。
vis[i] 表示当前物品转移到容量为i的时候 用掉了多少当前物品。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 105 #define maxm 100005 using namespace std; int w[maxn],num[maxn]; int vis[maxm]; bool dp[maxm]; int n,m; int main() { while(scanf("%d%d",&n,&m)!=EOF && n && m) { for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&num[i]); memset(dp,false,sizeof dp); dp[0]=1; int ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); for(int j=w[i];j<=m;j++) { if(!dp[j] && dp[j-w[i]] && vis[j-w[i]]<num[i])//如果dp[j]之前出现了 就不用加上来 {//要状态能够转移的话 要j-w[i]可达 而且转移之后不能比数量多 dp[j]=true; ans++; vis[j]=vis[j-w[i]]+1; } } } printf("%d\n",ans); } return 0; }