完全背包（经典dp）

柔光的暖阳◎ 2022-10-01 01:52 137阅读 0赞

完全背包  
时间限制：3000 ms | 内存限制：65535 KB  
难度：4  
描述  
直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO

输入  
第一行： N 表示有多少组测试数据（N<7）。  
接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0< M<=2000，0< V<=50000)  
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<.c<100000，0< w<100000)  
输出  
对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）  
样例输入  
2  
1 5  
2 2  
2 5  
2 2  
5 1  
样例输出  
NO  
1

### 题解： ###

**与01背包的区别：**  
**01背包：** *有N个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W 的物品，求所有挑选方案中价值总和的最大值*

**完全背包：** *有N个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有的挑选方案中价值总和的最大值，每件物品可选多个将完全背包转换为01背包*

dp\[i\]\[j\]=max(dp\[i-1\]\[j-k\*w\[i\]\]+k\*v\[i\]) (0<=k\*w\[i\]<=W)  
转化为一维数组 dp\[i\]=max(dp\[j-k\*w\[i\]\]+k\*v\[i\])\*\*

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 100000+5;
    struct rec
    {
        int c;
        int w;
    }vis[maxn];
    int n,m,v;
    long long dp[maxn];
    void DP()
    {
        for (int    i   =   1;  i   <=  m;  i++)
        {
            for (int    j   =   vis[i].c;j  <=  v;  j++)
               {
                   dp[j]    =   max(dp[j],  dp[j-vis[i].c]+vis[i].w);
               }
        }
    if(dp[v]<0)
     cout<<"NO"<<endl;
    else cout<<dp[v]<<endl;
    }
    int main()
    {
        cin>>n;
        while(n--)
        {
            memset(dp,-10000,sizeof(dp));//在01背包中初始化给的是0，这里要初始化一个比较大的负数
             dp[0]=0;
            cin>>m>>v;
            for(int i=0;i<m;i++)
            {
                cin>>vis[i].c>>vis[i].w;
            }
            DP();
        }
        return 0;
    }