【POJ】1742 coins 【背包问题】-白红宇

【POJ】1742 coins 【背包问题】

阅读量：5988 次

发布时间：2019-06-20

本文共 1285 字，大约阅读时间需要 4 分钟。

1 思路：

f[j](1<=j<=m)数组用来表示j是不是可以达到，现假设可达。b[j](1<=j<=m)数组用在第二层循环中，表示当价值为j时物品i已经用了几个。记录此值的原因：例如已经知道了j=10可以取到，现还有物品A价值2，数目2。不能通过此信息知道12、14可达，因为j=10可达的时候有可能已经把A这两个物品都用过了，所以需要记录此值，当b[10]=2时表明A已经用过2次了，不能再用了，故12、14都不能可达。现假设有一物品价值a[i]，数量为c[i]，若b[j-a[i]]

f[j-a[i]] == 1表明j-a[i]可以达到，且f[j]==0表示f[j]以前还没有取到过。j>=a[i]条件是必须的，否则不可能取这第i件物品。若上面条件同时满足，则说明j可以达到，设置f[j]=1, 此时i用的数目因为j的使用而多了一个，所以b[j]=b[j-a[i]]+1。

2 代码

#include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 110;const int maxm = 100010;int a[maxn], c[maxn], b[maxm];bool f[maxm];int n, m, ans;int main(int argc, char *argv[]){    int i, j;    while (scanf("%d%d",&n,&m) && n && m){        for(i=1; i<=n; i++) cin>>a[i];        for(i=1; i<=n; i++) cin>>c[i];        ans = 0;        memset(f, 0, sizeof(f));        f[0] = 1;        for(i=1; i<=n; i++){            memset(b, 0, sizeof(b));            for(j=1; j<=m; j++)                if(j>=a[i] && !f[j] && f[j-a[i]] && b[j-a[i]]+1<=c[i]){                    f[j]=1;                    b[j] = b[j-a[i]]+1;                    ans ++;                }        }        cout<
          
           <