0-1背包问题

问题描述

有\(N\)件物品和一个容量是\(V\)的背包。每件物品只能使用一次。

第\(i\)件物品的体积是\(v_i\)，价值是\(w_i\)。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式:

第一行两个整数\(N\)，\(V\)用空格隔开，分别表示物品数量和背包容积。\(0<N\),\(V\leq1000\)

接下来有\(N\)行，每行两个整数\(v_i,w_i\)用空格隔开，分别表示第 \(i\) 件物品的体积和价值。\(0<v_i,w_i\leq1000\)

输出格式:

输出一个整数，表示最大价值。

测试样例

Sample Input

4 7
1 2
2 4
3 4
4 5

Sample Output

11

问题分析

略

参考代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define w first
#define v second

int N,V;
vector<pair<int,int> > stuff(MAXN);
int res=0;

vector<int> dp(MAXN);

void getMaxValue(){
    for(auto &it:dp) it=0;//初始化数组

    for(int i=1;i<=N;i++){
        for(int j=V;j>=0;j--){
            if(j>=stuff[i].v) dp[j]=max(dp[j],dp[j-stuff[i].v]+stuff[i].w);
            else break;//装入物品
        }
    }
}

int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++)
        cin>>stuff[i].v>>stuff[i].w;
    getMaxValue();
    cout<<dp[V]<<'\n';
        return 0;
}

复杂度分析

时间复杂度分析

略

空间复杂度

略