关闭

运动鞋

标签: DP背包
144人阅读 评论(0) 收藏 举报
分类:

G: 运动鞋

时间限制: 1 Sec  内存限制: 128 MB

 

 

题目描述

经过几个月的艰苦学习,Iserlohn终于赢得了全额奖学金。作为一个运动鞋狂热爱好者,他决定用所有的钱在运动鞋商店进行消费。

有一些球鞋Iserlohn要收集,如Air Jordan Nike Pro。而每个品牌已发布各种产品。由于,Iserlohn绝对是一个运动鞋狂热,他意欲购买每个品牌至少有一个产品。

虽然每个产品的都有相应的定价,但是在Iserlohn心中也有一个价值倾向。由于他的钱有限,他希望最大限度地提高鞋的总价值。显然,作为一个收藏家,他不会购买相同产品的两次。

现在,Iserlohn需要你帮他找到他的答案,即在至少购买每个品牌的一个产品的情况下,使得所有运动鞋在他心中的总价值最高。

 

输入

1行包含三个整数NMK1<=N<=1001 <= M<= 100001<=K<=10)分别表示共有N种产品,M的钱和K种品牌。

接下来N行,每行三个整数abc1<=a<=k, 0<=b,c<100000)分别表示该商品属于哪种品牌,商品标价以及他心目中的价格。

 

输出

只有一个正整数,输出他心中的最大价值,如果不能满足他的要求,输出“Impossible”

 

样例输入

5 10000 3

1 4 6

2 5 7

3 4 99

1 55 77

2 44 66

样例输出

255

 

Solution

考虑到问题的描述:

K个品牌,花J元买的最大价值,且需要保证每种品牌至少一件产品。

转化成最优子结构就是:

F[i][j][k]表示前i个品牌,买到第i个品牌的第j件物品,花k元能买到的最大收藏价值,并且每种品牌至少购买一个产品。

显然,f[i][j][k]的最优解必定包括f[i-1][num[i-1]][k-w[i][j]]的最优解

或者f[i][j-1][k-w[i][j]]的最优解

或者f[i][j-1][k]的最优解

这也是能做出的3中决策——第j件物品为第i个品牌的第一件,不是第一件,或者不买第j件物品。这些决策实行的条件为前面的转移决策合法

决策合法当且仅当每种品牌至少购买一个产品

所以就有了状态转移方程式:

F[i][j][k]=max{F[i-1][num[i-1]][k-w[i][j]]+c[i][j] ,

      F[i][j-1][k-w[i][j]]+c[i][j], F[i][j-1][k]}

此处因为每个品牌都要有所以不能从f[i-1][num[i-1]][k]转移

具体实现时我们可以把f数组先全部置为-1,表示不合法

初始时的合法状态为f[0][0][k]=0   num[0]=0

考虑到此处可以像01背包一样进行空间上的优化

考虑把第二维省掉(因为后面两个式子去掉第一维跟01背包一样)

注意点是第三维度要倒序循环

在考虑一下能否把第一维度省掉

不能,因为第二维度不能匹配,且转移的是i-1num[i-1],可能被覆盖掉

不过可以考虑用滚动数组

时间复杂度:()  也就是  O(KNM)

空间复杂度:KM)   或者   M

 

离奇之处:

if (dp[i][k-w[i][j]]!=-1)

dp[i][k]=max(dp[i][k],dp[i][k-w[i][j]]+c[i][j]);

if (dp[i-1][k-w[i][j]]!=-1)

dp[i][k]=max(dp[i][k],dp[i-1][k-w[i][j]]+c[i][j]);

这两句话不能反过来,即必须先做f[i][k-w[i][j]]

此处的缘由我也不知道,WA了很多次

有人知道后望告知我。。。

 

知道了。。原因是价格可能为0,所以dp[i][k]=max(dp[i][k],dp[i][k-w[i][j]]+c[i][j]);

放在后面的话假如价格为零就先当本品牌第一个产品买了一次,然后又买了一次,造成双次购买,结果偏大(出题人好坑。)(来自hk同志的想法)


CODE

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

const int maxk=11,maxm=10010,maxn=105;
int dp[maxk][maxm],w[maxk][maxn],c[maxk][maxn],num[maxk];
int n,m,k;

void init()
{
	int a,b,cc;
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++)
	{
		cin>>a>>b>>cc;
		num[a]++;
		w[a][num[a]]=b;
		c[a][num[a]]=cc;		
	}
	memset(dp,-1,sizeof(dp));
	for (int i=0;i<=m;i++)
		dp[0][i]=0;	
}

void work()
{
	for (int i=1;i<=k;i++)
		for (int j=1;j<=num[i];j++)
			for (int k=m;k>=w[i][j];k--)
			{	
			if (dp[i][k-w[i][j]]!=-1)
				dp[i][k]=max(dp[i][k],dp[i][k-w[i][j]]+c[i][j]);
			if (dp[i-1][k-w[i][j]]!=-1)
				dp[i][k]=max(dp[i][k],dp[i-1][k-w[i][j]]+c[i][j]);
			}
}

void outit()
{
	if (dp[k][m]==-1) puts("Impossible");
	else cout<<dp[k][m];;	
}

int main()
{
	init();
	work();	
	outit();
}


0
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

求简单多边形面积时非常有用的“鞋带公式”

目的学习和介绍一个有用的求任意简单多边形面积的经典公式。 所谓“简单多边形”,可以是凹、或凸多边形,但原则上边与边之间不能有交叉;或者,拓扑一点,从多边形卷绕数的角度,多边形内的点卷绕数只能是±1\...
  • stereohomology
  • stereohomology
  • 2015-07-18 15:55
  • 2364

【钱柜娱乐开户开发】范例4-猜猜宝石放在哪个箱子里

实现"猜猜宝石放在哪个箱子"的小游戏:主界面中有三个箱子,单击其中任意一个箱子,将打开箱子,显示里面是否有宝石,并且将没有被单击的箱子设为半透明显示,被单击的鞋子正常显示,同时根据单击的箱子是否有宝石...
  • u013517797
  • u013517797
  • 2015-04-03 09:59
  • 1402

每个人都应该具有创业精神 ——《穿布鞋的马云》读后感

每个人都应该具有创业精神——《穿布鞋的马云》读后感 在阿里上市前夕,关注王利芬老师的微博,知道优米网要在阿里上市前夕出一本关于马云和阿里的书,王利芬老师参与执笔,甚是高兴。前不久买了这本书,今天周天一...
  • wojiushiwo987
  • wojiushiwo987
  • 2014-11-02 18:52
  • 3777

2018年最新款的女生智能运动鞋

我们常注意什么颜色、衣服款式、发型会让我们看起来老气或过时,对于这些地方小心翼翼,却忘了鞋履在整体穿搭中的重要性,我们总对鞋子有一种特殊的感情,例如:「经典款」、「百搭款」……等,也许你常觉得身上的搭...
  • Xmos2701
  • Xmos2701
  • 3天前 17:34
  • 7

程序员相亲,因一双运动鞋惨被拒绝

点击上方“CSDN”,选择“置顶公众号”关键时刻,第一时间送达!这个程序员,还是阿里高级研发工程师。寒冬时节,走在路途中,一位位「冲锋衣+牛仔裤+运动鞋+双肩包」的模特映入眼前,很多人第一反应,这是外...
  • csdnnews
  • csdnnews
  • 2018-01-09 00:00
  • 4499

2018年最新款的智能运动鞋

马上就要过年了,在外打拼的朋友已经陆陆续续踏上了回家的旅途。作为最重要的传统佳节之一,春节的传统习俗还在一直被传承下来,比如说年夜饭吃饺子、看春晚、走亲访友拜大年、过年穿新衣……   其实,过年穿新衣...
  • Xmos2701
  • Xmos2701
  • 2018-01-11 17:56
  • 55

adidas阿迪达斯运动鞋zencart免费模板有预览图

  • 2012-09-24 14:30
  • 3.76MB
  • 下载

Sneakerbot II运动鞋3d打印模型stl文件_跑鞋stl模型库3d打印技术网下载

  • 2014-03-14 15:07
  • 3.55MB
  • 下载

zencart模板 适合羽绒服 UGG 运动鞋等

  • 2012-09-24 15:24
  • 1.81MB
  • 下载

nike耐克运动鞋

  • 2012-09-24 14:28
  • 20.81MB
  • 下载
    个人资料
    • 访问:14601次
    • 积分:896
    • 等级:
    • 排名:千里之外
    • 原创:77篇
    • 转载:7篇
    • 译文:0篇
    • 评论:2条