特点：01背包同一物品只能取一次，完全背包同一物品可以取多次

题目描述：

方法1：二维dp

与01背包不同点：

• dp数组第一行初始化时不同

• 递推时，放物品i时处理情况不同，dp[i - 1][j - weight[i]] + value[i]变为dp[i][j - weight[i]] + value[i]

• 01背包由正上方与左上方推出，完全背包由正上方与同行左方推出

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int solve(int N,int V,vector<int> weight,vector<int> value){
    vector<vector<int>>dp(N,vector<int>(V+1,0));
    for(int i=weight[0];i<=V;i++) dp[0][i] = (i / weight[0]) * value[0];//初始化dp数组
    
    for(int i=1;i<N;i++){
        for(int j=1;j<=V;j++){//更新dp数组
            if(j<weight[i]) dp[i][j] = dp[i-1][j];//装不下
            else dp[i][j] = max(dp[i-1][j] , dp[i][j-weight[i]] + value[i]);//装得下
        }
    }
    return dp[N-1][V];
}

int main(){
    int N,V;
    cin>>N>>V;
    vector<int>weight(N,0);
    vector<int>value(N,0);
    for(int i=0;i<N;i++){
        cin>>weight[i];
        cin>>value[i];
    }
    
    int max_value = solve(N,V,weight,value);
    cout<<max_value<<endl;
    return 0;
}

方法2：一维dp

与01背包不同点：

• 因为01背包由正上方与左上方推出，完全背包由正上方与同行左方推出，所以一维迭代时，01背包得由右向左，完全背包得由左向右

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int solve(int N,int V,vector<int> weight,vector<int> value){
    vector<int>dp(V+1,0);
    for(int i=weight[0];i<=V;i++) dp[i] = (i / weight[0]) * value[0];//初始化dp数组
    
    for(int i=1;i<N;i++){
        for(int j=weight[i];j<=V;j++){//更新dp数组
            dp[j] = max(dp[j] , dp[j-weight[i]] + value[i]);//装得下
        }
    }
    return dp[V];
}

int main(){
    int N,V;
    cin>>N>>V;
    vector<int>weight(N,0);
    vector<int>value(N,0);
    for(int i=0;i<N;i++){
        cin>>weight[i];
        cin>>value[i];
    }
    
    int max_value = solve(N,V,weight,value);
    cout<<max_value<<endl;
    return 0;
}

• 一维dp时，装不下就不需要更新dp数组了