首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

poj 1742coins(优化的多重双肩包)

2012-10-20 
poj 1742coins(优化的多重背包)#includeiostreamusing namespace stdint dp[100005]int p[105],c[105]

poj 1742coins(优化的多重背包)

#include<iostream>using namespace std;int dp[100005];int p[105],c[105];int num[100005];int main(){ int i,j,k,n,m,cnt; while(scanf("%d%d",&n,&m),n+m) { for(i=0;i<n;i++) scanf("%d",&p[i]); for(i=0;i<n;i++) scanf("%d",&c[i]); for(i=1;i<=m;i++) dp[i]=0; dp[0]=1; cnt=0; for(i=0;i<n;i++) { for(j=0;j<=m;j++) num[j]=0; for(j=p[i];j<=m;j++) { if(!dp[j]&&dp[j-p[i]]&&num[j-p[i]]<c[i]) { num[j]=num[j-p[i]]+1; dp[j]=1; cnt++; } } } printf("%d\n",cnt); } return 0;}

热点排行