动态规划——完全背包问题（C++实现）

题目描述：

问题分析：

完全背包问题和01背包问题的不同点：

简单01背包中是从N个物品里选，每个物品只能用1次，完全背包则不同，每个物品可以用无限次。

01背包：

如果物品能放入背包（ j>=v[i]）则动态转移方程为 ：
dp[i][j]=max( dp[i-1][j]，dp[i-1][ j-v[i] ]+ w[i] )，
如果物品不能放入背包（j dp[i][j]=dp[i-1][j]

完全背包：

动态转移方程满足：dp[i][j]=max{dp[i-1][ j-k×v[i] ] + k×w[i]}，其中 0 ≤ k×v[i] ≤ j
可以发现，当k只能取0、1时的特例就是简单的0-1背包问题。

可以发现，选0次，即不选是肯定存在的，dp[i][j]=dp[i-1][j];
然后选1次，那就不一定存在了，可能可以选，也可能不可以选，假设可以选，在选0次该物品求出dp[i][j]的基础上，确定是否选该物品：if (j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
选2次、选3次，依次类推，一直到选k次。

代码和注释：

#include 
#define read(x,y) scanf("%d%d",&x,&y)
using namespace std;

int v[1010],w[1010];
int dp[1010][1010];//N行V列，0行0列初始为0

int main() 
{
    int N,V;
    //读入物品种类N和背包体积V
    read(N,V);
    //读入各个物品所占的体积和拥有的价值
    for (int i=1;i<=N;i++) 
        read(v[i],w[i]);
    
    for (int i=1;i<=N;i++)
        for (int j=0;j<=V;j++)
            //迭代k次
            for (int k=0;k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);

    printf("%d",dp[N][V]);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

结果展示：

进一步优化，参看：

https://blog.csdn.net/HangHug_L/article/details/114238728