算法学习笔记之基础dp之（0/1）背包问题

0/1背包是最经典的dp问题

背包问题：有多个物品，重量不同、价值不同，以及一个容量有限的背包，选择一些物品撞到背包中，问怎么装才能使装进背包的物品总价值最大。根据不同的的限定条件，可以报背包问题分为很多种，常见的有下面两种：

1. 如果每个物品可以切分，称为一般背包问题，用贪心法求最优解。比如吃自助餐，在饭量一定的情况下，怎么吃才能使吃到肚子里的最值钱？显然是从最贵的食物开始吃，吃完最贵的再吃第二贵的，这就是贪心。
   例如 圣诞老人的礼物-Santa Clau’s Gifts OpenJ_Bailian - 4110

   圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，
   每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，
   请问圣诞老人最多能带走多大价值的糖果。
   Input
   第一行由两个部分组成，分别为糖果箱数正整数n(1 <= n <= 100)，驯鹿能承受的最大重量正整数w（0 < w < 10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。
   Output
   输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束。
   Sample Input
   4 15
   100 4
   412 8
   266 7
   591 2
   Sample Output
   1193.0

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

struct suger {
	int v,w;//v是价值，w是重量
	double x;//x是单个糖果的平均价值
}record[101];

bool cmp(const suger& a, const suger& b ) {
	return a.x > b.x;
}//自定义结构体排序，按照平均价值从大到小

int main()
{
	int n, W;
	scanf("%d %d", &n, &W);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &record[i].v, &record[i].w);
		record[i].x = record[i].v / record[i].w;
	}
	sort(record, record + n, cmp);
//	for (int i = 0; i < n; i++) {
//		printf("%d ", record[i].v);
//	}
	int sum = 0;
	double max = 0;
	for (int i = 0; i < n; i++) {
		sum += record[i].w;
		if (sum <= W) {
			max += record[i].v;
		}
		else if (sum > W) {
			max += ((W - sum + record[i].w) * record[i].x);
			break;
		}
	}
	printf("%.1f\n", max);
}

2. 如果每个物体不可分割，成为0/1背包问题。仍以自助餐为例，这次食物都是一份份的，每一份必须是吃完。如果最贵的一份超过你的饭量，那只好放弃。这种问题无法用贪心求最优解。

01背包问题描述：有编号分别为a,b,c,d,e的五件物品，它们占据的空间量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个空间量为10的背包，如何让背包里装入的物品具有最大的价值总和？
考虑i号物品放还是不放
1：
当i号物品要放入时，则f[i][v]=f[i-1][v-w[i]]+p[i],表示（p[i]表示i号物品的价值），前i-1次选择后所选物品放入容量为v-w[i]的背包所获得最大价值为f[i-1][v-w[i]]，加上当前所选的第i个物品的价值p[i]即为f[i][v]。

2
当i号物品不放入时吗，则f[i][j]=f[i-1][j]。则表示为前i-1次选择所得的最大的价值。

所以，我们可以得出01背包的递推公式：f[i][v] = max{f[i-1][v], f[i-1][v-w[i]]+p[i]}
模板：

for(int i = 1; i <= n; i++)
        {
            for(j = w[i]; j <= V; j++)
                f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
        }

一维数组优化：

for(int i=1;i<=n;i++)
{
    for(int c=V;c>=0;c--)
    {
        if(c>=v[i])
        f[c]=max(f[c],f[c-v[i]]+w[i]);
    }
}

例题：HDU 2602 Bone Collector

已知N个糖果的重量和价值. 我们有一个口袋, 最多可以装V重量的糖果. 问口袋最多能放多少价值的糖果进去?

Input
输入的第一行是T, 表示有T组数据.
每组数据由三行组成.
第一行包含两个整数N和V(N <= 1000, V <= 1000). N表示糖果的个数, V表示口袋的载重.
第二行包含N个整数, 表示每一颗糖果的价值.
第三行包含N个整数, 表示每一颗糖果的重量.

Output
对每一组数据, 输出口袋最终可以放进去糖果的价值.
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
直接套模板即可

#include<iostream>
#include<algorithm>
using namespace std;

struct Node {
	int val;
	int vol;
}node[1010];
int t, n, v;
int dp[1010][1010];

int ans()
{
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= v; j++) {
			if (node[i].vol > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - node[i].vol] + node[i].val);
		}
	}
	return dp[n][v];
}
int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> v;
		for (int i = 1; i <= n; i++) cin >> node[i].val;
		for (int i = 1; i <= n; i++) cin >> node[i].vol;
		cout << ans() << endl;
	}
	return 0;
}

背包问题还有其他例如完全背包和多重背包