0/1背包含义

有N件物品和一个容量为V的背包，每件物品有体积c[i]和价值W[i]，求这个背包能装下的最大价值。
在这里，每件物品只有一个，即只能放一次。

二维的状态转移

1
2
3
4
5
6
7
8
9
10
11
for(i = 1; i<=n; i++)  
{  
    for(j = v; j>=c[i]; j--)//在这里，背包放入物品后，容量不断的减少，直到再也放不进了  
    {  
        f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);  
    }  
    for(j = c[i]-1; j>=0; j--)  
    {  
        f[i][j]=f[i-1][j];  //放不进第i件物品后，直接转移上一阶的状态
    }  
}

即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
它有两种情况：
第一种是第i件不放进去，这时所得价值为:f[i-1][v]
第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）
最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define N 4008
struct staff{
    int w,v;
}ss[N];
int dp[N][N];
int main(){
    cout<<"how many staffs ? how large the bag ?"<<endl;
    int n,V;cin>>n;cin>>V;
    cout<<"puts in weight and values"<<endl;
    for(int i=1 ; i<= n ;i++)
        scanf("%d%d",&ss[i].w,&ss[i].v);
    //dp[i][j]表示依次选择到第i件物品时所占用了j的背包容量。
    for(int i=1 ; i<=n ;i++)
        for(int j=V ; j>=0 ; j-- ){
            if(j>=ss[i].w)dp[i][j]=max(dp[i-1][j],dp[i-1][j-ss[i].w]+ss[i].v);
            else dp[i][j]=dp[i-1][j];
        }
    printf("max value in bags is %d\n",dp[n][V]);
}

一维的dp

优化二维结构后
这里f[v]就相当于二位数组的f[i][v]。

1
2
3
4
5
6
7
for(i = 1; i<=n; i++)//01背包  
        {  
            for(j = v;j>=c[i];j--)  
            {  
                dp[j] = max(dp[j],dp[j-c[i]]+c[i]);  
            }  
        }