背包问题(一) -- 01背包

发表于 | 阅读数

题目：Magry的朋友很多 - 零食篇

题目描述

Magry有个好朋友Ricardo快要过生日了。Ricardo突然想到可以借生日坑蒙拐骗点东西出来，于是就找了Magry要他买零食当生日礼物。

Magry手上没那么多钱，不过想了想还是上了天猫超市搜了一波，被那么多吃的看的眼花缭乱头晕目眩不知所措，因为Ricardo只有一个要求，那就是东西尽量好吃，而且还不要有Ricardo不喜欢的东西。。。

Magry已经知道的是：卖的零食总共有n种，不过比较坑爹的是一种零食一个用户限购一件；每种商品的价格为x元，好吃程度为w。另外，Magry已经知道在那些零食中有一部分是Ricardo不喜欢的（也许是忌口，总之这个和零食的好吃程度毫无关联，甚至对于一部分好吃程度为0甚至是负数的黑暗料理Ricardo也很有可能喜欢吃）。然后，Magry身上总共只有k元。

现在，Magry想要的是：如何确定购买方案使得在Magry手上的k元不会被透支（即商品总额不大于k元）的情况下买到总的好吃程度最高并且没有Ricardo不喜欢的零食呢？

输入

多组测试数据。

每组数据第一行为一个数，为商品种类数n，0≤n≤10000
接下来n行，每行3个整数x,w,t，每行分别表示一种商品，x代表商品价格，w代表东西的好吃程度，t表示Ricardo喜不喜欢这个东西，1表示喜欢，0表示不喜欢。其中1≤x≤1000，w在int范围内。

还有最后一行，一个数，k，表示Magry手头的钱。0≤k≤100000

输出

对于每组数据，输出一行，一个数，表示Magry在手头的k元不被透支的情况下所购商品的最大好吃程度。

输入样例

1
2
3
4
5
6
7
2
3 61 1
7 101 0
100
1
10 1 0
2

输出样例

1
2
61
0

思路

关于 01 背包

顾名思义，01背包指放入背包的物品每一种只有一个，因此对于每一种物品都只有两个选择，放或者不放，所以我们可以遍历所有的物品，得出状态转移方程：f[m] = max(f[m], f[m-a[i].x]+a[i].w), 其中 f[m] 指花 m 元钱的时候能得到的最大好吃程度 ，a结构数组用来存放每一个物品的价格，好吃程度和喜不喜欢

关键：我们在里面的循环要通过状态转移方程得出所有的f[m]值，而这个循环必须是从最大钱数 k 递减到 a[i].x， 这是为什么呢？
因为对于每一个 m ,f[m]都是由钱数少于m的状态所得到的，所以如果有少到多，每一个物品都会出现放多个的情况(这就是完全背包的思路)
相信聪明的你一定懂了！！！

代码

这里是本蒟蒻的代码~

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
/* 
 Author: 王振
 Result: AC	Submission_id: 1838386
 Created at: Fri Sep 20 2019 22:24:18 GMT+0800 (CST)
 Problem_id: 474	Time: 2670	Memory: 4056
*/

#include <iostream>
#include <algorithm>
using namespace std;
struct thing{
	long long x,w,t;
}a[10005];
long long f[100005];
int main()
{
	int n;
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].w>>a[i].t;
			if(a[i].t==0||a[i].w<=0)
			{
				i--;
				n--;
			}
		}
		int k;
		cin>>k;
		for(int i=0;i<=k;i++)
		{
			f[i]=0;
		}
		for(int i=1;i<=n;i++)
		{
			for(int m=k;m>=a[i].x;m--)
			{
				f[m]=max(f[m],f[m-a[i].x]+a[i].w);
			}
		}
		cout<<f[k]<<endl;
	}
    return 0;
}

感谢观看~