1. 疯狂的采药 ( maze.cpp )
【问题描述】
????????明明是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是明明，你能完成这个任务吗？
????????注意：每种草药可以无限制地疯狂采摘。
【输入样式】
????????输入第一行有两个整数 T
（
1
≤
T
≤
100000
）和
M
（
1
≤
M
≤ 10000），用一个空格隔开，
T
代表总共能够用来采药的时间，
M
代表山洞里的草药的数目。接下来的 M
行每行包括两个在
1
到
10000
之间（包括
1
和
10000
）的整数，分别表示采摘某种草药的时间和这种草药的价值。
【输出样式】
????????输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【输入样例】
????????70? ?3
????????71? ?100
????????69? ?1
????????1? ? ?2
【输出样例】
????????140
【数据范围】
????????对于 30%
的数据，
M <= 1000
；
????????对于全部的数据，M <= 10000
，且
M*T<10000000
（别数了，
7
个
0
）。
【问题分析】
????????这个问题非常类似于原来的采药那个问题，采药那个是 01
背包问题，这里所不同的是每种草药有无限件，也就是说每种草药不再仅仅是取或不取了，而有取 0
件、
1
件、
2
件
……
很多很多种。
????????对于这种物品没有限制的背包问题，称作为完全背包问题，再来看看原来的01 背包问题的解决过程。
????????解决 01
背包问题的时候，我们采用的方法是从大的背包开始尝试加入当前物品（因为此时用到前面的背包，而前面背包并没有装入该种物品，所以此时当前背包中最多只会装入一件该物品（当然如果此时的方法没有其它好的话，该件物品可能不装入该背包中）。
????????对于完全背包问题，解决的基本思路与 01
背包问题一样，只是尝试背包不再是从大到小，而是从小到大，这样做恰好解决可以无限使用的问题，也就是说尝试当前背包的时候，前面的背包中完全有可能装了多个该物品，这样就实现了物品无限制的问题，也就是说完全背包问题就是 01
背包问题的变形，解决的方法与 01
背包问题一致，只是把背包改成从小到大就可以了。
#include <bits/stdc++.h>
using namespace std;
int bag[100001],t[10001],v[10001];
int main()
{
int tt,mm;
cin>>tt>>mm;
for (int i=0;i<mm;i++)
cin>>t[i]>>v[i];
for (int i=0;i<mm;i++)
for (int j=t[i];j<=tt;j++)
bag[j]=max(bag[j],bag[j-t[i]]+v[i]);
cout<<bag[tt]<<endl;
return 0;
}
2. 储蓄罐 ( save.cpp )
【问题描述】
????????猪猪储蓄罐里可以存放一些硬币，但是时间久了就不知道里面存了多少钱，除非打破它，问题是这么可爱的猪猪储蓄罐你舍不得打破！现在给出空罐子的重量和最满能装到多重，然后给出每种硬币的价值和重量，要在不打破它的情况下确认罐子里最少有多少钱？
【输入样式】
????????第 1
行，为两个正整数
E, F
（
1 ≤ E ≤ F ≤ 10,000
）空罐子的重量和最满能装到多重，两数用空格隔开。
????????第 2
行，一个整数
N
（
1 ≤ N ≤ 500
）表示硬币的种类。
????????以下 N
行，每行一两个数
p, w
（
(1 ≤ P ≤ 50,000, 1 ≤ W ≤ 10,000)
）表示硬币的价值和重量。
【输出样式】
????????输出只有一个正整数，表示储蓄罐装满最少有多少钱，若无法装满则输出 0
。
【输入样例 1】
????????10? 110
????????2
????????1? ? 1
????????30? 50
????????10? 110
【输入样例 2】
????????2
????????1? ? 1
????????50? 30
????????2
????????10??3
????????20? 4
【输出样例 1】
????????60
【输出样例 2】
????????0
#include <bits/stdc++.h>
using namespace std;
int p[501], w[501], bag[10001];
int main()
{
int e,f,n,ww;
cin>>e>>f;
ww=f-e;
cin>>n;
for (int i=0;i<n; i++)
cin>>p[i]>>w[i];
bag[0]=1;
for (int i=0;i<n;i++)
{
for (int j=w[i];j<=ww;j++)
{
if (bag[j-w[i]])
{
if (bag[j]!=0) bag[j]=min(bag[j],bag[j-w[i]]+p[i]);
else bag[j]=bag[j-w[i]]+p[i];
}
}
}
if (bag[ww]) cout<<bag[ww]-1<<endl;
else cout<<"0"<<endl;
}
3. 点菜 ( eat.cpp )
【问题描述】
????????明明请朋友去一家餐馆吃饭，最近手头有头紧张，口袋里只剩 M 元（M ≤ 10000），所以选择了一家低端餐馆。餐馆虽低端，但是菜品种类不少，有 N 种（N ≤ 100），第 i 种卖 ai 元（ai ≤ 1000）。由于是很低端的餐馆，所以每种菜只有一份。朋友们奉行“不把钱吃光不罢休”，所以朋友们点单一定刚好把明明身上所有钱花完。大家想知道有多少种点菜方法。
【输入样式】
????????第一行是两个数字，表示 N
和
M
。
????????第二行起 N
个正数
ai
（可以有相同的数字，每个数字均在
1000
以内）。
【输出样式】
????????一个正整数，表示点菜方案数，保证答案的范围在 int
之内。
【输入样例】
????????4 4
????????1 1 2 2
【输出样例】
????????3
#include <bits/stdc++.h>
using namespace std;
int a[501],bag[10001];
int main()
{
int n,m;
cin>>n>>m;
for (int i=0;i<n;i++)
cin>>a[i];
bag[0]=1;
for (int i=0;i<n;i++)
for (int j=m;j>=a[i];j--)
bag[j]+=bag[j-a[i]];
cout<<bag[m]<<endl;
return 0;
}