河北大学程序设计训练营

[TOC]

day23 0-1背包

题目

给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:

共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:

输出装入背包中物品的最大总价值。

输入样例:

在这里给出一组输入。例如：

1
2
3
4
5
6
5 10
2 6
2 3
6 5
5 4
4 6

输出样例:

在这里给出相应的输出。例如：

1
15

思路

【思考一】朴素解法：

在0-1背包问题中，我不能直接使用贪心算法，但是我们可以引入阶段的概念。设d(i,j)为“把第一个i，i+1,i+2….n个物品装到容量为j的背包中最大总重量”那么我们就很容易地就能写出状态转移方程：
$$
\mathrm{d} \mathrm{p}(\mathrm{i}, \mathrm{j})=\max {\mathrm{d} \mathrm{p}(\mathrm{i}+1), \mathrm{j}, \mathrm{d} \mathrm{p}(\mathrm{i}+1, \mathrm{j}-\mathrm{v}[\mathrm{i}])+\mathrm{w}[\mathrm{i}]}
$$
【思考二】滚动数组法：

反正都要分层我们可以用一种和上面对称的状态定义，用f（i，j）表示把前i个物品装到容量为j的背包中的最大总重量,同样我们可以很快地写出状态转移方程：

$$
f(i, j)=\max {f(i-1, j), f(i-1, j-v[i])+w[i]}
$$
仔细观察这个式子，我们不难发现f数组是从上往下。从右往左计算的。在计算f（i，j）之前,f[j]里保存的就是f（i-1,j）的值，而f[j-w]保存的是f(i-1，j)（j是逆序的），这样
$$
\mathrm{f}[\mathrm{j}]=(\max [\mathrm{j}], \mathrm{f}[\mathrm{j}-\mathrm{v}]+\mathrm{w})
$$
实际上把max{f(i-1,j),f(i-1,j-v)}保存在f[j]中，覆盖原来的f（i-1，j-V）

AC代码（滚动数组法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,c;
    cin>>n>>c;
    vector<int> dp(c+1);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        for(int j=c;j>=a;j--){
            dp[j]=max(dp[j],dp[j-a]+b);
        }
    }
    cout<<dp[c]<<endl;
    return 0;
}