01背包問題：
有N件物品和一個容量為v的背包。第i件物品的體積（質(zhì)量）是volume[i]，價值是value[i]。求解將哪些物品裝入背包可使價值總和（dp[ ]）最大。

01背包的特點(diǎn)就是：每種物品僅有一件，可以選擇放或不放。

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

理解：現(xiàn)在需要放置的是第i件物品，這件物品的體積（質(zhì)量）是c[i],價值是w[i],
因此f[i-1][v]代表的就是不將這件物品放入背包，
f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之后的總價值，
比較兩者的價值，得出最大的價值存入現(xiàn)在的背包之中。

模板例題：

[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;
}