01背包模板

01背包问题：
有N件物品和一个容量为v的背包。第i件物品的体积（质量）是volume[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和（dp[ ]）最大。

01背包的特点就是：每种物品仅有一件，可以选择放或不放。

核心代码：dp[i][v]=max(dp[i-1][v]，dp[i-1][v-c[i]]+w[i])

理解：现在需要放置的是第i件物品，这件物品的体积（质量）是c[i],价值是w[i],
因此f[i-1][v]代表的就是不将这件物品放入背包，
f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值，
比较两者的价值，得出最大的价值存入现在的背包之中。

模板例题：

[HDU - 2602](https://vjudge.net/problem/17434/origin)

代码：

#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[1005], volume[1010], value[1010];
int main()
{
    int i, j, n, v, k;
    scanf("%d", &k);
    while(k--)
    {
        memset(dp,0,sizeof(dp));
        memset(value,0,sizeof(value));
        memset(volume,0,sizeof(volume));
        scanf("%d%d", &n, &v);
        for(i=1; i<=n; i++)
        {
            scanf("%d", &value[i]);
        }
        for(i=1; i<=n; i++)
        {
            scanf("%d", &volume[i]);
        }

        for(i=1; i<=n; i++)
        {
            for(j=v; j>=volume[i]; j--)
            {
                if(dp[j]<dp[j-volume[i]]+value[i])
                {
                    dp[j]=dp[j-volume[i]]+value[i];
                }
            }
        }
        printf("%d\n", dp[v]);
    }
    return 0;
}

模板：

        for(i=1; i<=n; i++)
        {
            for(j=v; j>=volume[i]; j--)
            {
                if(dp[j]<dp[j-volume[i]]+value[i])
                {
                    dp[j]=dp[j-volume[i]]+value[i];
                }
            }
        }

01背包路径查找模板题

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{
    int volume, value;
    int id;
} v[10010];
int dp[10010], pre[100][10010];
int res[10010];
int main()
{

    int cnt=1;
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);

        memset(pre,0,sizeof(pre));
        memset(dp,0,sizeof(dp));
        memset(v,0,sizeof(v));
        memset(res,0,sizeof(res));

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d", &v[i].value, &v[i].volume);
            v[i].id=i;
        }

        for(int i=1; i<=m; i++)
            for(int j=n; j>=v[i].volume; j--)
                if (dp[j-v[i].volume]+v[i].value > dp[j])
                {
                    dp[j]=dp[j-v[i].volume]+v[i].value;
                    pre[i][j]=1;
                }

        int sum1=0, sum2=0, k=0;
        for(int i=m,j=n; i>0; i--)
        {
            if(pre[i][j]==1)
            {
                sum1+=v[i].value;
                sum2+=v[i].volume;
                res[k++]=v[i].id;
                j-=v[i].volume;
            }
        }

        printf("Case #%d:\n", cnt++);
        printf("%d %d\n", sum1, sum2);

        sort(res, res+k);
        for(int i=0; i<k; i++)
        {
            if(i!=0) printf(" ");
            printf("%d", res[i]);
            if(i==k-1) printf("\n");
        }
    }
    return 0;
}