poj 1742 coins

标签：背包 coins 我们 poj include 优化 转移 1742

Description

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

一个不求最优解而是求可行性的多重背包
最简单的思路就是按照多重背包的做法，但是把+=换成|=
复杂度不变，如果是直接拆分的话，复杂度很大，过不去
可以用二进制拆分或者优先队列优化，但是复习到这里的我虽然是还不会优先队列优化的啦

先贴一个tle版本

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <string.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,m,f[1000001],a[101],c[101];
int main()
{
    while(n=read())
    {
        int ans=0;
        m=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            c[i]=read();
        }
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=c[i];j++)
            {
                for(int k=m-a[i];k>=0;k--)
                {
                    if(k+a[i]<=m)//这里第一次写成了a[i]*j，然后错了，要注意
                    {
                        f[k+a[i]]|=f[k];
                    }
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            ans+=f[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

写之前其实没什么思路，写完了就有点感觉了
我们在这中间执行了大量的无效转移
有许多地方，原本就可以被凑出，但是依旧进行了转移
dp虽然保证了即使进行了无效转移，却不会因为这个无效转移形成一个新的搜索树
但是感觉依旧是有优化的空间的，我们的决策集合似乎是可以缩小的。

考虑这些无效转移的共性和特征

他们转移的终点是1

想不出其他的了。。。
看了书，发现不是这么优化的，对于决策集合的优化这方面似乎已经被dp给一网打尽了（对比普通枚举）
我们的优化还是从可行性这个要求上下手

因为我们使用的dp其实是针对普通的多重背包的，他的要求是最优解，但是我们的要求是可行性
所以应该会有优化空间（上面好像说过一次了）

这意味着，原本对于重量总和的要求直接消失，我们只要能够让他达到，怎么都好说
原本，我们为了让他留下最优情况，是会使用先前更优秀的情况来和现在的情况进行比较来进行更新的，很明显，现在完全不需要
只要他能够达到，我们就计数，这就够了
所以，这个变化带来的第一个变化就是，我们不需要因为这个无效转移形成一个新的搜索树，正如上面所说，这一点没有优化空间

但是，还有一点，就是，因为最优解不做要求，我们转移时不需要考虑谁更优秀，所以大量的对比不在需要，如果一个点他已经可以被组合出来
我们就不需要考虑它在多考虑了一种硬币的情况下能不能再被考虑，但如果是面对之前的最优解情况，我们需要。
因为通过这一种硬币，我们很可能是能够拿到一种更优秀的情况的，所以需要进行转移的尝试

对于这一点变化，我们要如何进行优化？

首先，最简单的，就是如果这一种数值已经能够被组合出来了，那我们就不需要在进行从前面转移过来的尝试。

然后，对于能够新组合的情况，我们就转移，但是，我们可以向后转移，然后再转移的时候，记录下转移到了这种情况用了几枚这种硬币，在用完时不再转移。
这样就能够保证所有情况都被尽可能的覆盖到了。并且，优化了一个循环，就是sigema(c[i])的复杂度

但是在真正的多重背包中，这样的转移自然是不可行的。因为如果使用这种硬币和前面的硬币适当的组合下，能够让结果更优秀，那肯定是要使用的。
但是这里面则是直接考虑，能用就直接全用上，用到用不了为止。

真正的多重背包里面，这很不合理，因为如果这种东西更重，也就是使用它付出的代价更高，那我们使用它自然是不优秀的
但是这题目没有代价
能用就用，就看你能组合几种情况。

 

我写这些的目的其实是为了在下次遇到这个题目的时候能够不是通过记忆，而是通过一些更通用的办法来自己推导出来做法
但是现在看来我好像失败了
我不知道这么才能想到
怎么样才能意识到，在价值这个限制消失后，这个题目的模型发生的变化能够让我做什么事情。

好难

有可能是我对最优解和可行性的理解不够深刻
也许我不应该一上来就套上多重背包的算法，从头开始设计也许更好？
不知道

我应该要意识到，在代价消失时，我们之前合理组合达到的最优解，其实作为状态的其实不是代价了

最优解其实是作为了一个限制，而且是非常严苛的限制

之前我们需要那一重枚举使用个数的循环，是因为我们需要把所有可能最优的情况都枚举出来
现在不需要，是因为我们现在的硬币没有代价，能够转移到这个位置的状态，没有优劣之分
所以我们完全不需要去考虑那些已经能够被接触到的状态能否再次被转移，他们现在完全只是我们通过这个硬币来接触到其他状态的跳板
我要做的就只有好好利用那些能够带我到新的状态的跳板，避开那些没有用的跳板。
如果一个转移的末尾，已经被接触了，那自然是完全没有意义的，但是在真正的多重背包里面，有意义
所以在真正的多重背包里面，我们就需要去枚举了
因为它有更严苛的要求
所以我们在这种题目里面是不需要对每一个都考虑全部的转移的，优化就来自这里

嗯

感觉有一点感觉了

好了

现在感觉之前没想出来是因为不知道这个枚举的转移的真正含义和作用
现在应该是有点感觉了
好啦，应该把这方面能学的学了

这个优化，比起说它是转移方式的优化，我更倾向把它作为一种对dp的重新设计。
因为它有一个维度的含义其实改变的，只不过最终的结果和原来的多重背包有点相似而已

上面就是我的思考过程了
有些混乱
但是结果是好的，无所谓

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <string.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,m,f[100001],a[100001],c[100001],used[100001];
int main()
{
    while(n=read())
    {
        int ans=0;
        m=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            c[i]=read();
        }
        memset(f,0,sizeof(f));
        f[0]=1;
        memset(used,0,sizeof(used));
        for(int i=1;i<=n;i++)
        {
            memset(used,0,sizeof(used));
            for(int k=0;k<=m-a[i];k++)
            {
                if(f[k]==1&&f[k+a[i]]==0&&used[k]<c[i])
                {
                    f[k+a[i]]=1;
                    used[k+a[i]]=used[k]+1;
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

标签：背包,coins,我们,poj,include,优化,转移,1742
From： https://www.cnblogs.com/HLZZPawa/p/17760462.html