背包九讲-01背包

动态规划核心思维能力

动态规划是求最优解问题的重要解法，也是信息学奥赛中每年必考的内容之一。
学习动态规划更应该注重此类问题思维能力的锻炼，多多做题，一般>50题后方可入门。
注意理解以下概念
1、状态
2、状态属性
3、状态的计算，也就是状态转移
4、优化：DP的优化都是代码的等价代换

下面的题目建议看视频，能更透彻的理解！

01背包开胃菜

1、[装箱问题]–填满型有限01背包

题目描述
有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出格式
1个整数，表示箱子剩余空间。
输入
24
6
8
3
12
7
9
7
输出
0

【详细讲解】

2、等和数列–填满型无限01背包

题目描述
【问题描述】
有n个数列，每个数列各自选若干个数，使得每个数列的和一样大，并且这个和要尽量大。
【输入文件】
第一行是一个整数N（N<=100），表示一共有n个数列。
以下N行每行是一个系列非负整数，表示每个数列的数字，用-1结束。
一个数列中的数字个数不超过100个，每个数也不超过100。
【输出文件】
一个整数，表示使得每个数列的和一样大，并且这个和要尽量大的值。如果找不到合适的方案，则输出0。
输入
输出
样例输入
2
2 1 -1
3 2 1 -1
样例输出
3

#include<bits/stdc++.h>
using namespace std;
bool f[11000];//每个序列所能达到的和 
int a[110];
int tot[11000];//所有序列所能达到的和 
int main()
{
	int n,sum;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)//循环输入n个序列 
	{
		int x,len=0;
		while(scanf("%d",&x)!=EOF)
		{
			if(x==-1) break;
			a[++len]=x;//len为该序列的长度 
		}
		sum=0;
		memset(f,false,sizeof(f));
		f[0]=true;
		for(int j=1;j<=len;j++)//逐一处理每个序列所能达到的和sum 
		{
			for(int k=sum;k>=0;k--)
			{
				if(f[k]==true)
				{
					f[k+a[j]]=true;
					sum=max(sum,k+a[j]);
				}
			}
		}
		for(int i=0;i<=sum;i++) if(f[i]) tot[i]++;//记录每个序列所能达到的和 
		
	}
	for(int i=sum;i>=0;i--)
	if(tot[i]==n) 
	{
		printf("%d\n",i);
		break;
	}
	return 0;
}

0-1背包

【问题描述】
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci ，得到的价值是 Wi 。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
【输入格式】
第 1 行两个正整数，分别表示 N 和 V，中间用一个空格隔开。
第 2 行 N 个正整数，表示 Ci ，中间用一个空格隔开。
第 3 行 N 个正整数，表示 Wi ，中间用一个空格隔开。
其中：1≤N≤100，1≤V≤10⁶ ，1≤Ci ≤10000，1≤Wi ≤10000。
【输出格式】
一行一个正整数，表示最大的价值总和。
【输入样例】
4 20
8 9 5 2
5 6 7 3
【输出样例】
16

【问题解析】
定义f[i][j]表示取第i件物品后的体积为j，所获得最大价值。

【视频讲解】

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 110;
int n, V;
int w[MAX_N], c[MAX_N];
int f[MAX_N + 1][1000010];
int main() {
	cin>>n>>V;
	for (int i = 1; i <= n; i++) {
		cin>>c[i];
	}
   for (int i = 1; i <= n; i++) {
		cin>>w[i];
	}
	memset(f, 0, sizeof(f));	
	for(int i = 1;i<=n;i++)
		for(int j = 0;j<=V;j++)
		{
			if(j<c[i])
				f[i][j]=f[i-1][j];
			else
				f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
		}
	
	cout<<f[n][V];
}

【空间优化】

#include<cstdio>
using namespace std;
const int maxm = 2001, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxm]; 
int main()
{
    scanf("%d%d",&m, &n);            //背包容量m和物品数量n
    for (int i=1; i <= n; i++)
        scanf("%d%d",&w[i],&c[i]);     //每个物品的重量和价值
   
    for (int i=1; i <= n; i++)                //设f(v)表示重量不超过v公斤的最大价值
        for (int v = m; v >= w[i]; v--)
            if (f[v-w[i]]+c[i]>f[v])
                f[v] = f[v-w[i]]+c[i];
printf("%d",f[m]);                      // f(m)为最优解
return 0;
}

更多练习

1、采药
视频讲解
2、小毛的交易
视频讲解
3、开心的金明
视频讲解
4、猪猪储蓄罐
视频讲解
5、Hay For Sale S
视频讲解