Week12-动态规划（二）_给定 n 件物品,物品的重量为 w[i],物品的价值为 c[i]。现挑选物品放入背包中,假定

A : 01背包

题目描述
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述
第一行为N(1≤N≤5000)(1≤N≤5000)，V(1≤V≤5000)(1≤V≤5000)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤10
3
)，ci(1≤c[i]≤10
3
)，用一个空格分隔。

输出描述
输出只有一个数，最大总价值。

Case 1
Input
10 9
7 1
8 10
7 10
7 7
7 6
3 7
4 1
3 3
9 1
1 4
Output
14

#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[50001],w[10001],v[10001],W,n;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{

	memset(dp, 0, sizeof(dp));
	scanf("%d%d", &n,&W);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &w[i], &v[i]);
	//对第i个物品进行选择，从大于第i个物品的背包承重量开始，进行计算。之所以使for (int j = W; j >=w[i]; j--) j倒着来，是因为一维数组要进行数据覆盖。
	for (int i = 1; i <=n; i++)
	for (int j = W; j >=w[i]; j--)
		dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	cout <<dp[W] << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

B : 完全背包

题目描述
有N种物品（每种有无限多个）和一个容量为V的背包。第i种物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述
第一行为N(1≤N≤5000)(1≤N≤5000)，V(1≤V≤5000)(1≤V≤5000)。

下面N行，第i行描述第i种物品的wi(1≤w[i]≤10
3
)，ci(1≤c[i]≤10
3
)，用一个空格分隔。

输出描述
输出只有一个数，最大总价值。

Case 1
Input
10 8
4 5
1 1
1 5
5 4
5 10
6 5
1 1
5 6
7 4
4 5
Output
40

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#define MAXN 6000
using namespace std;
int w[MAXN];
int c[MAXN];
int f[MAXN];
int main()
{
    int N, V;
    cin>>N>>V;
    for(int i=1; i<=N; i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1; i<=N; i++){
        for(int j=w[i]; j<=V; j++){
            f[j] = max(f[j],f[j-w[i]]+c[i]);
        }
    }
    cout<<f[V]<<endl;
}
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

C : 多重背包

题目描述
有N种物品和一个容量为V的背包。第i种物品的重量是w[i]，价值是c[i]，有k[i]个。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述
第一行为N(1≤N≤10^4)(1≤N≤10
4
)，V(1≤V≤10^4)(1≤V≤10
4
)。

下面N行，第i行描述第i种物品的wi(1≤w[i]≤10
2
)，ci(1≤c[i]≤10
6
)，ki(1≤k[i]≤10
2
)，用一个空格分隔。

输出描述
输出只有一个数，最大总价值。

Case 1
Input
6 1
7 10 4
6 9 1
6 8 1
10 6 2
9 8 3
1 3 2
Output
3

#include <iostream>

typedef long long lld;

lld vs[56666];
lld ps[56666];
lld f[56666];
unsigned long ki = 0;

void load(lld n)
{
    lld vi, pi, ci;
    for (lld i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld", &vi, &pi, &ci);
        for (lld v = 1; v <= ci; v <<= 1)
        {
            ki++;
            vs[ki] = v * vi;
            ps[ki] = v * pi;
            ci -= v;
        }
        if (ci > 0)
        {
            ki++;
            vs[ki] = ci * vi;
            ps[ki] = ci * pi;
        }
    }
}

int main()
{
    lld N, V;
    scanf("%lld %lld", &N, &V);
    load(N);
    for (lld i = 1; i <= ki; i++)
    {
        for (lld j = V; j >= vs[i]; j--)
        {
            f[j] = std::max(f[j], f[j - vs[i]] + ps[i]);
        }
    }
    printf("%lld\n", f[V]);
    return 0;
}
    
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

D : 分组背包

题目描述
有N件物品和一个容量为V的背包，将所有的物品划分成若干组，每个组里面的物品最多选一件。第i件物品的重量是w[i]，价值是c[i]，属于组k[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述
第一行为N(1≤N≤10^3)(1≤N≤10
3
)，V(1≤V≤10^3)(1≤V≤10
3
)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤10
2
)，ci(1≤c[i]≤10
6
)，ki(1≤k[i]≤10
2
)，用一个空格分隔。

输出描述
输出只有一个数，最大总价值。

Case 1
Input
7 9
6 6 3
5 10 3
3 5 1
9 4 4
6 1 4
8 3 5
5 2 2
Output
15

#include <iostream>

typedef long unn;

unn vs[100][1000];
unn ps[100][1000];
unn Gl[100];
unn ans[100][1000];
bool sd[100][1000];

unn f(unn k, unn j)
{
    if (k < 0) return 0;
    if (sd[k][j]) return ans[k][j];
    sd[k][j] = true;
    unn m = f(k - 1, j);
    for (unn i = 0; i < Gl[k]; i++)
    {
        if (j >= vs[k][i] &&f(k - 1, j - vs[k][i]) + ps[k][i] > m)
        {
            m = f(k - 1, j - vs[k][i]) + ps[k][i];
        }
    }
    ans[k][j] = m;
    return m;
}


int main()
{
    unn N, V;
    std::cin >> N >> V;
    for (unn i = 0; i < N; i++)
    {
        unn vi, pi, ki;
        std::cin >> vi >> pi >> ki;
        vs[ki][Gl[ki]] = vi;
        ps[ki][Gl[ki]] = pi;
        Gl[ki]++;
    }
    std::cout << f(100, V);
    return 0;
}
    
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

E : 超大背包

题目描述
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述
第一行为N(1≤N≤40)(1≤N≤40)，V(1≤V≤10^{15})(1≤V≤10
15
)。

下面N行，第i行描述第i个物品的wi(1≤w[i]≤10
15
)，ci(1≤c[i]≤10
15
)，用一个空格分隔。

输出描述
输出只有一个数，最大总价值。

Case 1
Input
3 225274242
70498827 830583485
72910089 759360759
80945586 1095298545
Output
2685242789
Case 2
Input
27 1405406868
500580317 1559925714
1191095816 2052289019
2086671060 125049457
1467200227 1826963529
1054830291 1055178046
457445390 293196664
1428828824 1163887408
27108927 353186119
354284919 1641947343
1044113045 1319050872
814300917 42212882
802287458 2142953934
1178508095 943859578
2133693898 163905627
1687820729 1091482274
737249638 2121489517
1203304272 1081378899
581034126 832395967
1370524005 487337507
178833685 1328104836
512934928 897959032
1629846549 1677014752
2011536830 64430283
547991487 1683026867
2125422226 728351378
744805340 261154211
1909716650 317131682
Output
5466192232

#include <bits/stdc++.h>
#define INF 0x3fffffff
typedef long long ll;
using namespace std;
const int MAXN = 42;
int N;
ll V;
ll w[MAXN],c[MAXN];
pair<ll,ll> p[1<<(MAXN/2)];
int main() {
    ios::sync_with_stdio(false);
    cin >> N >> V;
    for(int i=0;i<N;i++)
    {
        cin>>w[i]>>c[i];
    }
    
    int n=N/2;
    for(int i=0;i<1<<n;i++)
    {
        ll prew=0,prec=0;
        for(int j=0;j<n;j++)
        {
            if(i>>j&1)
            {
                prew+=w[j];
                prec+=c[j];
            }
        }
        p[i]=make_pair(prew,prec);
    }
    sort(p,p+(1<<n));
    int m=1;
    for(int i=1;i<1<<n;i++)
    {
        if(p[m-1].second<p[i].second)
        {
            p[m++]=p[i];
        }
    }
    ll res=0;
    for(int i=0;i<1<<(N-n);i++)
    {
        ll prew=0,prec=0;
        for(int j=0;j<N-n;j++)
        {
            if(i>>j&1)
            {
                prew+=w[n+j];
                prec+=c[n+j];
            }
        }
        if(prew<=V)
        {
            ll tc=(lower_bound(p,p+m,make_pair(V-prew,(ll)INF))-1)->second;
            res=max(res,prec+tc);
        }
    }
    cout<<res;
    return 0;
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

思路

这里描述的已经很详细了

课上用的补充资料在上面，几乎涵盖了各种问题。

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中
每种物品都只有一件。

令dp[i][j]来表示前i件物品装入容量为j的背包所能得到的最大总价值。

对于dp[i][j]来说，i指的是前i件物品，j指的是还剩下多少背包空间。于是对于dp[i][j]来说，有公式

编号i 重量w[i] 价格v[i] 背包容量 W = 20
1 2 3
2 3 4
3 4 5
4 5 8
5 9 10

表格标红的地方就是我们要求的dp[5][20]
接下来对表格每个位置进行说明，那第一行来说，表示的是前0件物品，背包容量为0~20时可以放进去的最大价值，物品都没有，不管容量多大可以容纳的价值都是0；
同样的，比如第二行，表示前1件物品（此物品重量为2，价值为3）在背包剩余容量为0时，放不下去，此时最大价值是0；背包剩余容量是1时，放不下去，此时最大价值是0；背包剩余容量为2时，能放进去，此时最大价值是3···
那么到了第3行（前2件物品），在背包容量是5的时候，为了达到最大价值，可以把第1件和第2件商品都放进去，5 >= 2 + 3，可以放下，最大价值为3 + 4 = 7。
整个表格的填写由程序来完成，计算公式为上面所列出的dp[i][j]计算公式。最后只需要取出我们所需要的dp[5][20]即可得到前5件物品，背包容量为20时的最大价值。

这个问题很经典，网上有大量的博客和理解，下面还有一个通俗的理解：

Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝

第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。

涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（F 数组）之后得到。
还有，如果要求的是“总价值最小”“总件数最小”，只需将状态转移方程中的 max改成 min 即可。