背包问题之多重背包

http://soj.sysu.edu.cn/show_problem.php?pid=1001&cid=1769

其实感觉多重背包比01背包和完全背包都要难，每件物品的数量可能不止一件，还是求放入背包的物品的最大价值。

在背包九讲中，给出的动态转移方程为：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

但是感觉还是考虑边界问题比较烦人，所以我想的是把多重背包和之前的01背包联系起来......不知道行不行

这里我写了一种一维dp数组的写法，在这题测试是tle的，因为这题的数据量太大，怎么解决后面再说......

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a[10];
int w[10]={3, 5, 2, 6, 11, 8};
double v[10]={0.01, 0.05, 0.10, 0.25, 0.50, 1};
double dp[10005];
//double dp[15][10005];

int main()
{
    int m;
    while(scanf("%d", &m) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        int n=6;
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
        //一维 
        for(int i=0; i<n; i++)
            for(int j=0; j<a[i]; j++) //相当于把物品分成一件一件
                for(int k=m; k>=w[i]; k--)
                       dp[k] = max(dp[k-w[i]]+v[i], dp[k]);
        //二维  
        /* 
        for(int i=1; i<=n; i++)
            for(int j=0; j<=m; j++)
                for(int k=0; k<=a[i]; k++)
                {
                    if(j >= k*w[i])    
                        dp[i][j] = max(dp[i-1][j-k*w[i]]+k*v[i], dp[i][j]); 
                }
              */
        printf("$%.2lf
", dp[m]);
        //printf("$%.2lf
", dp[n][m]);
    }
    return 0;
}

看注释那一行就相当于把相同的这几件物品分成一件件，然后套用01背包的方法来解决！

那要怎么解决超时问题呢？

用到了二进制划分的办法，分成1,2,4,8,16...64.....（剩下的）

假如物品有12件，就分成1,2,4,5（这里的5就是剩下的），这样，如果我想拿7件，就用1+2+4来凑就好了，只用遍历3次，而不是7次！省了好多时间！

最后还是用01背包解决！

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a[15];
double dp[15000];
int weight[15]={3, 5, 2, 6, 11, 8};
double value[15]={0.01, 0.05, 0.10, 0.25, 0.50, 1};
int w[15000];
double v[15000];

int main()
{
    int N=6;
    int m;
    while(scanf("%d", &m) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        int count = 0;
        for(int i=0; i<N; i++)
            scanf("%d", &a[i]);
            
        for(int i = 0; i < N; ++i)
        {
            for(int j = 1; j <= a[i]; j <<= 1) // 二进制拆分
            {
                w[count] = j * weight[i];
                v[count++] = j * value[i];
                a[i] -= j;
            }
            if(a[i] > 0)
            {
                w[count] = a[i] * weight[i];
                v[count++] = a[i] * value[i];
            }
        }
        for(int i = 0; i < count; ++i)  // 使用01背包
            for(int j = m; j >= w[i]; j--)
                dp[j] = max(dp[j-w[i]]+v[i], dp[j]);
        printf("$%.2lf
",dp[m]);
    }  
    return 0;
}