01背包问题+例题_二维背包问题例题

目录

QUESTION：

解法：

二维数组：时间复杂度和空间复杂度都是O(n*V）

一维数组：时间复杂度O(n*V),空间复杂度O(V)

例题：

ac代码：

---

QUESTION：

---

有n件物品（每种物品都只有一件），w[i]表示物品的重量，v[i]表示物品的价值，现有一个容量为V的背包，应该如何选物品使得书包内装的物品的value之和最大呢？

 

解法：

---

二维数组：时间复杂度和空间复杂度都是O(n*V）

对于第i个物品，有选和不选两种情况

dp[i][j]表示在容量为j的情况下选取i个物品的最大value值

核心代码：

for(i=0;i<n;i++)
    for(j=V;j>=w[i];j--)
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

一维数组：时间复杂度O(n*V),空间复杂度O(V)

核心代码：

for(i=0;i<n;i++)
   for(j=V;j>=w[i];j--)
       dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

注意：

用二维数组存的话j的枚举是顺序还是逆序都没有关系

但是用一维数组存的话j的枚举顺序必须是逆序，即从大到小

 

举个例子：

V=8

如果按照顺序（j从小到大枚举),dp数组初始化为0

当i=1时

dp[2]=max(dp[2],dp[0]+3)=3;

dp[3]=max(dp[3],dp[1]+3)=3;

dp[4]=max(dp[4],dp[2]+3)=6;

dp[5]=max(dp[5],dp[3]+3)=6;

当容量为4时，dp[4]的值为6，它是由dp[3]+3的到的，且dp[3]=3，意思是它实际上选了两次“i=1”这个物品，那么结果显然是错的。而正巧，顺序枚举j正好完全背包问题的解法（每种物品由无穷件）。

但是如果逆序枚举的话：

dp[5]=max(dp[5),dp[3]+3);dp[5]和dp[3]之前都没有出现过，所以dp[5]=3,值是正确的（dp[3]的值的改变是在dp[5]之后）

 

例题：

---

hdoj2602:Bone Collector  典型的01背包问题

ac代码：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define ll long long int
#define maxn 1005
using namespace std;
int v[maxn],w[maxn],dp[maxn];
int main()
{
    int t,n,V,i,j,ans;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&n,&V);
        for(i=0;i<n;i++)
            scanf("%d",&v[i]);
        for(i=0;i<n;i++)
            scanf("%d",&w[i]);
        for(i=0;i<n;i++)
            for(j=V;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        printf("%d\n",dp[V]);
    }
    return 0;
 
}