「动态规划」完全背包问题入门

上一篇提到的是01背包问题我们本篇要提的是完全背包问题完全背包问题与01背包问题十分的相似什么是01背包问题呢所谓0就表示不选 1就表示选及选和不选的背包问题而完全背包与01背包是十分相似的区别就是01背包的选最多选一次也就意味着每件物品只有一件而正因完全完全也就意味着每件物品是有至多件的，所以完全背包问题是每件物品可以供多次选择的，那么下面我们就说说处理该种问题的基本思路。

我们还是直接拉题来看吧，本篇是一道入门题，照应标题，用来介绍该类问题的思路。

有 N

种物品和一个容量是 V

的背包，每种物品都有无限件可用。

第 i

种物品的体积是 v**i，价值是 w**i

。

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

输入格式

第一行两个整数，N，V

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

接下来有 N

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

种物品的体积和价值。

输出格式

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

数据范围

0<N,V≤1000

0<v**i,w**i≤1000

输入样例

输出样例：

好，以上就是原题，下面附上代码和思路。

# include <stdio.h>

int main(void){
   
    int N,V;//如题目要求输入
    scanf("%d %d",&N,&V);
    int v[N],w[N];//v 代表体积 w = worth 价值
    int i;
    for(i = 0;i < N;++i){
   
        scanf("%d %d",&v[i],&w[i]);//赋值
    }
    int dp[N][V+1];//该处数组含义 dp[5][6]表示前6种物品 在体积为6的背包中能装得最大价值
    for(i = 0;i <= V;++i){
   
        dp[0][i] = 0;
        if(i >= v[0]){
   
            dp[0][i] = (i/v[0]) * w[0];//出口
        }
    }
    int j; 
    for(i = 1;i < N;++i){
   
        for(j = 0;j <= V;++j){
   
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i])
                dp[i][j] = dp[i - 1][j] > (dp[i][j-v[i]] + w[i])?dp[i - 1][j] : (dp[i][j-v[i]] + w[i]);//转移方程
        }
    }
    printf("%d",dp[N-1][V]);
    return 0;
}

下面在来一段优化的代码：一维数组的实现

# include <stdio.h>
# define X 10000
int dp[X];
int main(void){
   
    int N,V;
    scanf("%d %d",&N,&V);
    int v[N],w[N];
    int i;
    for(i = 0;i < N;++i){
   
        scanf("%d %d",&v[i],&w[i]);
    }
    for(i = 0;i <= V;++i){
   
        if(i >= v[0]){
   
            dp[i] = (i/v[0]) * w[0];
        }
    }
    int j;
    for(i = 1;i < N;++i){
   
        for(j = v[i];j <= V;++j){
   //思考这里为什么是正序 和 01背包问什么不同呢？思考倒序能不能ac呢？
            dp[j] = dp[j] > (dp[j - v[i]] + w[i])?dp[j]:(dp[j - v[i]] + w[i]);
        }
    }
    printf("%d",dp[V]);
    return 0;
}

本题还有一种方法于下一篇多重背包一块展开讨论。第二篇啊，刚开始写写的可能不是那么具体得当，不足希望大佬们能够指出。

「动态规划」完全背包问题 入门