Massive Algorithms: Jobdu 1455：珍惜现在，感恩生活

Jobdu 1455：珍惜现在，感恩生活 - HDOJ 2191

九度笔记之 1455：珍惜现在，感恩生活 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？

输入：: 输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

输出：: 对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

样例输入：

1
8 2
2 100 4

4 100 2

样例输出：

https://www.cnblogs.com/tgycoder/p/5329424.html

http://www.cnblogs.com/tanhehe/articles/2998736.html
X. 二进制解法

int main()  
{  
    int nCase,Limit,nKind,i,j,k,  
        v[111],w[111],c[111],dp[111];  
    //v[]存价值，w[]存尺寸，c[]存件数  
    //在本题中，价值是米的重量，尺寸是米的价格  
  
    int count,Value[1111],size[1111];  
    //count存储分解完后的物品总数  
    //Value存储分解完后每件物品的价值  
    //size存储分解完后每件物品的尺寸  
  
    cin>>nCase;  
    while(nCase--)  
    {     
        count=0;  
        cin>>Limit>>nKind;  
        for(i=0;i<nKind;i++)  
        {  
            cin>>w[i]>>v[i]>>c[i];  
              
            //对该种类的c[i]件物品进行二进制分解  
            for(j=1;j<=c[i];j<<=1)  
            {  
                //<<右移1位，相当于乘2  
                Value[count]=j*v[i];  
                size[count++]=j*w[i];  
                c[i] -= j;  
            }  
            if(c[i] > 0)  
            {  
                Value[count]=c[i]*v[i];  
                size[count++]=c[i]*w[i];  
            }  
        }  
  
        //经过上面对每一种物品的分解，  
        //现在Value[]存的就是分解后的物品价值  
        //size[]存的就是分解后的物品尺寸  
        //count就相当于原来的n  
  
        //下面就直接用01背包算法来解  
        memset(dp,0,sizeof(dp));  
  
        for(i=0;i<count;i++)  
            for(j=Limit;j>=size[i];j--)  
                if(dp[j] < dp[j-size[i]] + Value[i])  
                    dp[j]=dp[j-size[i]]+Value[i];  
          
        cout<<dp[Limit]<<endl;  
    }  
    return 0;  
}

inline void ZeroOnePack(int w,int v)  
{  
    int j;  
    for(j=limit;j>=w;j--)  
    {  
        if(f[j-w]+v > f[j])  
            f[j]=f[j-w]+v;  
    }  
}  
  
inline void CompletePack(int w,int v)  
{  
    int j;  
    for(j=w;j<=limit;j++)  
    {  
        if(f[j-w]+v > f[j])  
            f[j]=f[j-w]+v;  
    }  
}  
  
inline void MultiplePack(int w,int v,int amount)  
{  
    if(amount * w >= limit)  
    {  
        CompletePack(w,v);  
        return ;  
    }  
    for(int k=1;k<amount;k<<=1)  
    {  
        ZeroOnePack(k*w,k*v);  
        amount -= k;  
    }  
    ZeroOnePack(amount*w,amount*v);  
}  
  
int main()  
{  
    int T,n;  
    cin>>T;  
    while(T--)  
    {  
        cin>>limit>>n;  
          
        for(int i=0;i<n;i++)  
            cin>>weight[i]>>Value[i]>>num[i];  
          
        memset(f,0,sizeof(f));  
          
        for(i=0;i<n;i++)  
            MultiplePack(weight[i],Value[i],num[i]);  
          
        cout<<f[limit]<<endl;  
    }  
    return 0;  
}

第一种方法，把相同的大米单独考虑 在本题中，不同种类的大米含有固定数量的袋数，我们可以把同一种类不同袋的大米单独看作一个物品，比如A类大米有4袋，我们就可以看作4个不同种类的大米，只不过他们的价格，重量是一样的。然后按照背包问题，用动态规划做就行了。参考题目1209：最小邮票数

void getMax(){
int money;
int riceClass;
std::cin>>money>>riceClass;
std::vector<int> ricePrice;
std::vector<int> riceWeight;
int price;
int weight;
int num;
for(int rid = 0;rid<riceClass;rid++){
std::cin>>price>>weight>>num;
ricePrice.insert(ricePrice.end(),num,price);
riceWeight.insert(riceWeight.end(),num,weight);
}
int *dp = new int[money+1];
for(int i = 0;i<money+1;i++)
dp[i] = 0;
std::vector<int>::size_type riceNum = ricePrice.size();
for(std::vector<int>::size_type rn = 0;rn<riceNum;rn++){
for(int m = money; m>=ricePrice.at(rn); m--)
dp[m] = max(dp[m], dp[m-ricePrice.at(rn)]+ riceWeight.at(rn));
}
std::cout<<dp[money]<<std::endl;
}
void judo(){
int c = 0;
while(std::cin>>c){
for(int i = 0;i<c;i++)
getMax();
}
}

http://blog.csdn.net/superlc320/article/details/18975493

int main()

{

    int C;

    scanf("%d", &C);

    while(C--)

    {

        Food a[2010];

        int dp[110];

        int n, m;

        while(scanf("%d%d", &n, &m) != EOF)

        {

            int i, j, c;

            for(i = 0; i < m; i++)

            {

                scanf("%d%d%d", &a[i].price, &a[i].weight, &c);

                while(--c)  //将多袋粮食分开，将多重背包问题转化为01背包问题

                {

                    i++;

                    m++;

                    a[i] = a[i-1];

                }

            }

            memset(dp, 0, sizeof(int)*110);           //动态规划数组初始化

            for(i = 0; i < m; i++)                     //动态规划

                for(j = n; j >= a[i].price; j--)       //此处必须从大到小

                    dp[j] = max(dp[j - a[i].price] + a[i].weight , dp[j]);

            printf("%d\n", dp[n]);

        }

    }

    //system("pause");

    return 0;

}

第二种方法，利用二进制取数优化
假设某个物品有10个数量，我们取数的方法是先取1个，再取2个，再取4个以此类推（i=1;i<=10;i<<=1）；

也就是说，会取到1、2、4个，然后最后还会剩下3个。观察前面3个数，它们任意相加又可以组成3、5、6、7，这些数再与最后深下的3相加又可以得到8、9、10
也就是说，1到10全有了，但是我们操作的次数却从10次降低到了4次！

参见二进制取数在多重背包和母函数中的应用

关键代码如下，分别选择2^n 个，注意

1，循环的终止条件为nr<=leftNum leftNum表示还剩该大米的袋数

2，每次循环 leftNum-=nr

该循环的意思就是依次从 riceNum[rid]袋大米中拿走1，2，……nr 袋大米进行规划，

int leftNum = riceNum[rid];
for(int nr = 1; nr<=leftNum; nr<<1){
for(int m = money; m>= nr*ricePrice[rid]; m--)
dp[m] = max(dp[m], dp[m - nr*ricePrice[rid]] + nr*riceWeight[rid]);
leftNum-=nr;
}

如果大米还有剩余则，对剩余的大米一袋袋拿走进行规划

if(leftNum==0){
continue;
}
for(int nr = 1; nr<=leftNum; nr<<1){
for(int m = money; m>= nr*ricePrice[rid]; m--)
dp[m] = max(dp[m], dp[m - nr*ricePrice[rid]] + nr*riceWeight[rid]);
}

void getMax(){
int money;
int riceClass;
std::cin>>money>>riceClass;
int price;
int weight;
int num;
for(int rid = 0;rid<riceClass;rid++){
std::cin>>ricePrice[rid]>>riceWeight[rid]>>riceNum[rid];
}
int *dp = new int[money+1];
for(int i = 0;i<money+1;i++)
dp[i] = 0;
for(int rid = 0;rid<riceClass;rid++){
int leftNum = riceNum[rid];
for(int nr = 1; nr<=leftNum; nr<<1){
for(int m = money; m>= nr*ricePrice[rid]; m--)
dp[m] = max(dp[m], dp[m - nr*ricePrice[rid]] + nr*riceWeight[rid]);
leftNum-=nr;
}
if(leftNum==0){
continue;
}
for(int nr = 1; nr<=leftNum; nr<<1){
for(int m = money; m>= nr*ricePrice[rid]; m--)
dp[m] = max(dp[m], dp[m - nr*ricePrice[rid]] + nr*riceWeight[rid]);
}
}
std::cout<<dp[money]<<std::endl;
}

http://www.cnblogs.com/ka200812/archive/2011/08/06/2129505.html

一个关于多重背包的问题，即给定每个物品的价格和数量，在有限背包中求得可以装进背包的最大价值，一般的做法就是将多重背包转化为诺干个01背包来解决，例如某个物品有1000个，则转化为将这个物品看成1000个只有一个数量的该物品，然后运用01背包，容量反向动规求的解！可是如果某个物品的数量是1W、10W或者是100W，那么岂不是要求上W个01背包了，不超时才怪。

那么有什么好办法可以解决这样的问题呢？从上面的方法中我们看出，我们处理问题的方法是一个一个处理物品，物品有1W个，我们便处理1W次。这样做的好处是编程方便，并且把每个物品都遍历到了，不会有错。可是太慢了。如果我们不是一次取一个，而是一个取很多个，同时我们保证我们取数过程中不会出现丢三落四的情况，那不就爽歪歪了吗？

这里介绍一种办法，用来满足上面的要求。二进制取数！

假设某个物品有10个数量，我们取数的方法是先取1个，再取2个，再取4个以此类推（i=1;i<=10;i<<=1）；

也就是说，会取到1、2、4个，然后最后还会剩下3个。观察前面3个数，它们任意相加又可以组成3、5、6、7，这些数再与最后深下的3相加又可以得到8、9、10

也就是说，1到10全有了，但是我们操作的次数却从10次降低到了4次！

for(i=0;i<m;i++) //m种物品

{

    left=num[i]; //每个物品的数量

    for(j=1;j<=left;j<<=1) //二进制取数

{

        /*do something by yourself*/

        left-=j;

}

    if(left)  //剩余的数

{

        /*do something by yourself*/

}

}

    while(t--)
    {
        cin>>n>>m;
        for(i=0;i<m;i++)
        {
            cin>>p[i]>>w[i]>>b[i];
        }
        memset(f,0,(n+1)*4);
        for(i=0;i<m;i++)
        {
            left=b[i];
            for(j=1;j<=left;j<<=1)
            {
                for(k=n;k>=j*p[i];k--)
                {
                    f[k]=max(f[k],f[k-j*p[i]]+j*w[i]);
                }
                left-=j;
            }
            if(left)
            {
                for(k=n;k>=left*p[i];k--)
                {
                    f[k]=max(f[k],f[k-left*p[i]]+left*w[i]);
                }
            }
        }
        cout<<f[n]<<endl;
    }

http://www.wutianqi.com/?p=537

    while(nCases--)
    {
        memset(nMultiplePack, 0, sizeof(nMultiplePack));
        scanf("%d %d", &nValue, &nKind);
        for(int i=0; i<nKind; ++i)
            scanf("%d %d %d", &value[i], &weight[i], &bag[i]);
        for(int i=0; i<nKind; ++i)
            for(int j=0; j<bag[i]; ++j)
                for(int k=nValue; k>=value[i]; --k)
                    if(nMultiplePack[k] < nMultiplePack[k-value[i]]+weight[i])
                        nMultiplePack[k] = nMultiplePack[k-value[i]] + weight[i];
        printf("%d\n", nMultiplePack[nValue]);
 
    }

http://www.cnblogs.com/easonliu/p/3904161.html

22 void refresh() {
23     for (int i = 0; i < c; ++i) {
24         for (int j = n; j >= p; --j) {
25             if (dp[j-p] >= 0) {
26                 dp[j] = max(dp[j], dp[j-p] + h);
27             }
28             res = max(res, dp[j]);
29         }
30     }
31 }
32  
33 int main() {
34     cin >> C;
35     for (int i = 0; i < C; ++i) {
36         init();
37         cin >> n >> m;
38         for (int j = 0; j < m; ++j) {
39             cin >> p >> h >> c;
40             refresh();
41         }
42         cout << res << endl;
43     }
44     return 0;
45 }

Read full article from 九度笔记之 1455：珍惜现在，感恩生活 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

Jobdu 1455：珍惜现在，感恩生活 - HDOJ 2191

Labels

Popular Posts