「动态规划」多重背包问题入门

前两篇分别说了01背包问题和完全背包问题正如标题我们这篇说一下背包问题的最后一类多重背包问题

先说一下什么是多重背包问题：多重背包问题就是一件物品有有限件然后找出能取的最大价值。

与之前一样通过例题说明思想。

# include <stdio.h>
int dp[150][150];
int main(void){
    int N,V;
    scanf("%d %d",&N,&V);
    int v[N],s[N],w[N];
    int i;
    for(i = 0;i < N;++i){
        scanf("%d %d %d",&v[i],&w[i],&s[i]);
    }
    int j;
    int k;
    for(i = 0;i <= V;++i){//出口
        if(i >= v[0] && i/v[0] <= s[0]){
            dp[0][i] = (i/v[0]) * w[0];
        }
        else if(i >= v[0]){
            dp[0][i] = k * w[0];
        }
        else{
            dp[0][i] = 0;
        }
    }
    for(i = 1;i < N;++i){
        for(j = 0;j <= V;++j){
            for(k = 0;k*v[i] <=j && k <= s[i];++k){
                dp[i][j] = dp[i][j]>(dp[i - 1][j - k * v[i]] + k*w[i])?dp[i][j]:(dp[i - 1][j - k * v[i]] + k*w[i]);//状态转移方程
            }
        }
    }
    printf("%d",dp[N - 1][V]);
    return 0;
}

好这就是这道题的代码看下你们能不能看懂

下面在写一种优化方式读者们想一想如果是有限个的话是否能转成01背包问题答案是当然能

当然我猜你们想得是不是本来有5件现在分成5个一件但请你们再从复杂度想这样是不是其实并没有优化多少

现在给你们看一道思维题：小王家要粉刷墙壁，他请了一位工人这位工人告诉他这个粉刷墙壁的工程期是7天，现在小王手上有一根金条，但小王每天都要给工人付工资，请问小王如何切割三次金条能满足自己的要求？

答案是这样的小王可以将金条分成1/7 2/7 4/7 这样的话是不是就能够组合出任意数了呢？

这个题的优化也是如此，请读者们想一想我们该如何完成数的划分？

好下面看一道这一道题

有 N 种物品和一个容量是 V

的背包。

第 i

种物品最多有 s**i 件，每件体积是 v**i，价值是 w**i

。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V

，用空格隔开，分别表示物品种数和背包容积。

接下来有 N

行，每行三个整数 v**i,w**i,s**i，用空格隔开，分别表示第 i

种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V≤2000
0<v**i,w**i,s**i≤2000

提示：

本题考查多重背包的二进制优化方法。

输入样例

输出样例：

该题与第一题的格式什么的都是相同的但不难发现该题的数据范围是要大于第一题的，读者们下去可以试试用第一题的代码提交本体，肯定是不能通过得！本篇列举的三个题来自acwing 4、5、6题感兴趣的可以再去做一次这个题看你是否能够ac这些题。

# include <stdio.h>
int dp[2500];//思考为什么要使用一维来做
int main(void){
   
    int N,V;
    scanf("%d %d",&N,&V);
    int v[N + 1],s[N + 1],w[N + 1];
    int i,j;
    for(i = 1;i <= N;++i){
   
        scanf("%d %d %d",&v[i],&w[i],&s[i]);
    }
    int k,ans = 1;
    int vv[300000] = {
   0},ww[300000] = {
   0};
    for(i = 1;i <= N;++i){
   //看一下这里的代码处理
        for(k = 1;k <= s[i];k = k * 2){
   
            vv[ans] = k * v[i];
            ww[ans++] = k * w[i];
            s[i] = s[i] - k;
        }
        vv[ans] = s[i] * v[i];
        ww[ans++] = s[i] * w[i];
    }
    for(i = 1;i <= ans - 1;++i){
   
        for(j = V;j >= vv[i];--j){
   
            dp[j] = dp[j] > (dp[j - vv[i]] + ww[i])?dp[j] : (dp[j - vv[i]] + ww[i]);
        }
    }
    printf("%d",dp[V]);
    return 0;
}

好这就是第一次优化的代码。

行今天写的有点困了下一种优化结合下一篇的路线问题一起说。
下一种优化依靠队列实现，看到的读者可以思考一下该如何去做呢？状态转移方程该怎样写呢？

「动态规划」 多重背包问题 入门