dp动态规划动归经典问题买书问题01背包

买书问题 dp实现 题目：买书 有一书店引进了一套书，共有3卷，每卷书定价是60元，书店为了搞促销，推出一个活动，活动如下： 如果单独购买其中一卷，那么可以打9.5折。 如果同时购买两卷不同的，那么可以打9折。 如果同时购买三卷不同的，那么可以打8.5折。 如果小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少需要多少钱呢？（x、y、z为三个已知整数）。 1、过程为一次一次的购买，每一次购买也许只买一本（这有三种方案），或者买两本（这也有三种方案）， 或者三本一起买（这有一种方案），最后直到买完所有需要的书。 2、最后一步我必然会在7种购买方案中选择一种，因此我要在7种购买方案中选择一个最佳情况。 3、子问题是，我选择了某个方案后，如何使得购买剩余的书能用最少的钱？并且这个选择不会使得剩余的书为负数 。母问题和子问题都是给定三卷书的购买量，求最少需要用的钱，所以有"子问题重叠"，问题中三个购买量设置为参数， 分别为i、j、k。 4、的确符合。 5、边界是一次购买就可以买完所有的书，处理方式请读者自己考虑。 6、每次选择最多有7种方案，并且不会同时实施其中多种，因此方案的选择互不影响，所以有"子问题独立"。 7、我可以用minMoney[i][j][k]来保存购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱。 8、共有x * y * z个问题，每个问题面对7种选择，时间为：O( x * y * z * 7) = O( x * y* z )。 9、用函数MinMoney(i,j,k)来表示购买第1卷i本，第2卷j本，第3卷k本时所需的最少金钱，那么有： MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分别为对应的7种方案使用的最少金钱： s1 = 60 * 0.95 + MinMoney(i-1,j,k) s2 = 60 * 0.95 + MinMoney(i,j-1,k) s3 = 60 * 0.95 + MinMoney(i,j,k-1) s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k) s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1) s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1) s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)

#include

#define MAX 8888

using namespace std;

int xyz;
int mm[50][50][50];

int min（int s1int s2int s3int s4int s5int s6int s7）
{
	int mini=s1;
	if （s2	if （s3	if （s4	if （s5	if （s6	if （s7	return mini;
}

int MinMoney（int iint jint k）
{
	int s1s2s3s4s5s6s7s8s9; 
	if （i==0&&j==0&&k==0） return 0;
	if （i!=0） s1 = 60 * 0.95 + MinMoney（i-1jk）; else s1=MAX;
	if （j!=0） s2 = 60 * 0.95 + MinMoney（ij-1k）; else s2=MAX;
	if （k!=0） s3 = 60 * 0.95 + MinMoney（ijk-1）; else s3=MAX;
	if （i!=0&&j!=0） s4 = （60 + 60） * 0.9 + MinMoney（i-1j-1k）; else s4=MAX;
	if （i!=0&&k!=0） s5 = （60 + 60） * 0.9 + MinMoney（i-1jk-1）; else s5=MAX;
	if （j!=0&&k!=0） s6 = （60 + 60） * 0.9 + MinMoney（ij-1k-1）; else s6=MAX;
	if （i!=0&&j!=0&&k!=0） s7 = （60 + 60 + 60） * 0.85 + MinMoney（i-1j-1k-1）; else s7=MAX;
	return min（s1s2s3s4s5s6s7）;
}

int main（void）
{
	cin>>x>>y>>z;
	cout<	return 0;
}

/*
题目：买书
有一书