poj 1742 Coins 多重背包变形
题目：http://poj.org/problem?id=1742
用bool dp[i]来表示价格i是否能被表示出。
直接做：
#include <cstdio>#include <iostream>using namespace std;const int max_s = 107;bool f[100007];int w[max_s],b[max_s];//f[i]来表示当前i价格是否出现过，int sum[100007];//当价格达到i时，最多使用这一种硬币的次数int main(){ int n,V,i,j; while(scanf("%d%d",&n,&V),n+V) { int ans=0; for(i=0;i<n;i++) scanf("%d",&w[i]); for(i=0;i<n;i++) scanf("%d",&b[i]); for(i=f[0]=1;i<=V;i++) f[i]=0; for(i=0;i<n;i++) { for(j=0;j<=V;j++) sum[j]=0;//关键是用sum来限定了次数 for(j=w[i];j<=V;j++)//从w[i]到V循环检查看是否能够出现前边没有出现的价格 { if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i]) //如果j价格没有出现过，且j-w[i]出现过，并且使用i硬币的次数没有超出给定的数量 { f[j]=1;//标记为已出现过 sum[j]=sum[j-w[i]]+1;//使用次数+1 ans++; } } } cout<<ans<<endl; }}