先上代码,和01背包问题的解法有略微的改动,区别在于遍历体积 jj 时从逆序改为顺序,在上一题中有我关于01背包问题的理解。
上一篇代码中(01背包中),解释过,逆序是为了保证更新当前状态时,用到的状态是上一轮的状态,保证每个物品只有一次或零次;
在这里,因为每个物品可以取任意多次,所以不再强求用上一轮的状态,即本轮放过的物品,在后面还可以再放;
不妨按照思路,模拟一遍过程。
首先dp数组初始化全为0:给定物品种类有4种,包最大体积为5,数据来源于题目的输入
v[1] = 1, w[1] = 2
v[2] = 2, w[2] = 4
v[3] = 3, w[3] = 4
v[4] = 4, w[4] = 5

i = 1 时: j从v[1]到5
dp[1] = max(dp[1],dp[0]+w[1]) = w[1] = 2 (用了一件物品1)
dp[2] = max(dp[2],dp[1]+w[1]) = w[1] + w[1] = 4(用了两件物品1)
dp[3] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] = 6(用了三件物品1)
dp[4] = max(dp[4],dp[3]+w[1]) = w[1] + w[1] + w[1] + w[1] = 8(用了四件物品1)
dp[5] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] + w[1] + w[1] = 10(用了五件物品)

i = 2 时:j从v[2]到5
dp[2] = max(dp[2],dp[0]+w[2]) = w[1] + w[1] = w[2] =  4(用了两件物品1或者一件物品2)
dp[3] = max(dp[3],dp[1]+w[2]) = 3 * w[1] = w[1] + w[2] =  6(用了三件物品1,或者一件物品1和一件物品2)
dp[4] = max(dp[4],dp[2]+w[2]) = 4 * w[1] = dp[2] + w[2] =  8(用了四件物品1或者,两件物品1和一件物品2或两件物品2)
dp[5] = max(dp[5],dp[3]+w[2]) = 5 * w[1] = dp[3] + w[2] =  10(用了五件物品1或者,三件物品1和一件物品2或一件物品1和两件物品2)

i = 3时:j从v[3]到5
dp[3] = max(dp[3],dp[0]+w[3]) = dp[3] = 6 # 保持第二轮的状态 
dp[4] = max(dp[4],dp[1]+w[3]) = dp[4] = 8 # 保持第二轮的状态 
dp[5] = max(dp[5],dp[2]+w[3]) = dp[4] = 10 # 保持第二轮的状态

i = 4时:j从v[4]到5
dp[4] = max(dp[4],dp[0]+w[4]) = dp[4] = 10 # 保持第三轮的状态
dp[5] = max(dp[5],dp[1]+w[4]) = dp[5] = 10 # 保持第三轮的状态

上面模拟了完全背包的全部过程,也可以看出,最后一轮的dp[m]即为最终的返回结果。  
但是这个题具体还是有点区别,当然核心思想是问完全背包
而第二问是要求刚好放满的最大体积所以只需要再加一行代码予以判断~~~
if(j%v[i] == 0 || dp2[j] != 0) dp2[j+v[i]] = max(dp2[j+v[i]], dp2[j] + w[i]);
滴滴滴滴滴-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------分割线
然后是具体的代码如下:
#include<bits/stdc++.h>
using namespace std;
int main (){
    ios::sync_with_stdio(false);
    int n, V;
    cin>>n>>V;
    vector<int> v(n+1), w(n+1);
    vector<int> dp1(V+1), dp2(V+1);
    for(int i = 1; i <= n; ++i){
        cin>>v[i]>>w[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= V - v[i]; ++j){
            dp1[j+v[i]] = max(dp1[j+v[i]], dp1[j] + w[i]);
            if(j%v[i] == 0 || dp2[j] != 0) dp2[j+v[i]] = max(dp2[j+v[i]], dp2[j] + w[i]);
        }
    }
    cout<<dp1[V]<<endl;
    cout<<dp2[V]<<endl;

    return 0;
}