01背包问题模板

01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有一件。

令 dp[i][j] 表示前 i 件物品装入容量为 j 的背包所能得到的最大总价值。

对于 dp[i][j] 来说，i 指的是前 i 件物品，j 指的是还剩下多少背包空间。于是对于dp[i][j]来说，有公式

经典01背包裸题

例题：hdu 2602 Bone Collector

一般做法：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{
    int val,vol;
}a[1010];
int dp[1010][1010];
int main(){
    int t;  cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        int n,v;    cin>>n>>v;
        for(int i=1;i<=n;i++)
            cin>>a[i].val;
        for(int i=1;i<=n;i++)
            cin>>a[i].vol;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=v;j++){
                if(a[i].vol>j)  dp[i][j]=dp[i-1][j];
                else dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].vol]+a[i].val);
            }
        }
        cout<<dp[n][v]<<endl;
    }
}

滚动数组优化：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{
    int val,vol;
}a[1010];
int dp[1010];      //表示该容量背包的最大价值
int main(){
    int t;  cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        int n,v;    cin>>n>>v;
        for(int i=1;i<=n;i++)
            cin>>a[i].val;
        for(int i=1;i<=n;i++)
            cin>>a[i].vol;
        for(int i=1;i<=n;i++){
            for(int j=v;j>=a[i].vol;j--)    //反过来循环，避免被覆盖
                dp[j]=max(dp[j],dp[j-a[i].vol]+a[i].val);
        }
        cout<<dp[v]<<endl;
    }
}