背包模板（01背包，完全背包）

01背包

发现一个01背包讲的比较好的博主，就是为什么取一次要用倒序：http://t.csdn.cn/A8efr

描述

你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为v_ivi​ ,价值为w_iwi​。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数v_ivi​和w_iwi​，表示第i个物品的体积和价值。

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入：

3 5
2 10
4 5
1 4

复制输出：

14
9

复制说明：

装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。 

示例2

输入：

3 8
12 6
11 8
6 8

复制输出：

8
0

复制说明：

装第三个物品时总价值最大但是不满，装满背包无解。 

备注：

要求O(nV)的时间复杂度，O(V)空间复杂度

#include <iostream>
#include<string.h>
using namespace std;
int v[1005];
int w[1005];
int dp[1005];
int main() {
 
    int n,V;
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)
        {
            dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
        }
    }
    printf("%d\n",dp[V]);
   
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
 
    if (dp[V] < 0) dp[V] = 0;
    printf("%d\n",dp[V]);
    return 0;
}

完全背包

描述

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为v_ivi​ ,价值为w_iwi​。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数v_ivi​和w_iwi​，表示第i种物品的体积和价值。

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入：

2 6
5 10
3 1

复制输出：

10
2

复制

示例2

输入：

3 8
3 10
9 1
10 1

复制输出：

20
0

复制说明：

无法恰好装满背包。

示例3

输入：

6 13
13 189
17 360
19 870
14 184
6 298
16 242

复制输出：

596
189

复制说明：

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

#include <stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int v[1005];
int w[1005];
int dp[1005];
int main() {
    int n,V;
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;i++)
    {
         for(int j=v[i];j<=V;j++)
         {
             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
         }
    }
    printf("%d\n",dp[V]);
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=V;j++)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    if(dp[V]<0) dp[V]=0;
    printf("%d\n",dp[V]);
    return 0;
}