完全背包问题

DP42 【模板】完全背包

描述

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为𝑣𝑖vi​ ,价值为𝑤𝑖wi​。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数𝑣𝑖vi​和𝑤𝑖wi​，表示第i种物品的体积和价值。

1≤𝑛,𝑉≤10001≤n,V≤1000

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

思路：

就是在01背包的基础上进行扩展，本质上与01背包的区别就是dp[i][j]的可能取值出现了更多中可能。但dp所表示的含义是不变的，改变的只有初始化和dp[i][j]的构成。

dp[i][j]=max(dp[i-1][j-k*v[i]+k*w[i])(k=0,1,2.....)，只要j-k*v[i]>=0下标合法，就有可能是由这个dp组成dp[i][j]的最大值。但是，此处没有必要将所有的k的可能取值都遍历一遍，因为对于dp[i-1][j-1*v[i]]+w[i]*1,dp[i-1][j-2*v[i]]+w[i]*2,dp[i-1][j-3*v[i]]+w[i]*3,......dp[i-1][j-k*v[i]+k*w[i],可以看成是dp[i-1][j-v[i]]+w[i]，则dp[i][j]=max(dp[i][j],dp[i][j-vi[i]]+wi[i] ).

初始化：

对于第一问，要求dp[i][j]为前i个不超过j的最大值，因此i=0或j=0全为0即可。

对于第二问，要求dp[i][j]为前i个刚好为j的取值，j=0时为0，其余全为-1（因为i为0的时候，j为非0一定取不到）；

#include <iostream>
#include<vector>
#include<math.h>
using namespace std;

int main() {
  
    int n,v;
    cin>>n>>v;

    vector<int>vi(n+1);
    vector<int>wi(n+1);

    for(int i=1;i<=n;i++)
    {
        cin>>vi[i]>>wi[i];
    }
    
    vector<vector<int>>dp(n+1,vector<int>(v+1));

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=v;j++)
        {       
            dp[i][j]=dp[i-1][j];
                  if(j -vi[i] >= 0)
                dp[i][j]=max(dp[i][j],dp[i][j-vi[i]]+wi[i] );
            
        }
    }
   
  cout<<dp[n][v]<<endl;
    vector<vector<int>>dps(n+1,vector<int>(v+1,-1));
    for(int j=0;j<=n;j++ )
    dps[j][0]=0;

    	for (int i = 1; i <= n; i++)
							{
								for (int j = 1; j <= v; j++)
								{
									int k = 1;
									dps[i][j] = dps[i - 1][j];
									// while (j - k * vi[i] >= 0 )
									// {   
									// 	if( dps[i - 1][j - k * vi[i]] != -1)
									// 	dps[i][j] = max(dps[i][j], dps[i - 1][j - k * vi[i]] + wi[i] * k);
									// 	k++;
									// }
                                    if(j -vi[i] >= 0&&dps[i][j -vi[i]]!=-1)
                                    dps[i][j]=max(dps[i][j],dps[i][j-vi[i]]+wi[i] );
								}
							}

    if(dps[n][v]!=-1)
  cout<<dps[n][v];
   else
   cout<<0;











}
// 64 位输出请用 printf("%lld")