频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 3033 I love sneakers! (01背包+反分组背包)
2014-05-04 11:11:56         来源:HDU 3033 I love sneakers! (01背包+反分组背包)  
收藏   我要投稿


题意:给你 n,m,k,表示有k种鞋子共n双,你有m的容量;


每双鞋子有容量p和价值v;问是否买全k种鞋子,若能在容量为m的情况下最多能买到鞋子的价值为多少;


每双鞋子只能买一次(01背包),每种鞋子至少买一种(分组背包:每组只能有一个)与传统分组背包的限制相反。


注意初始化!!!


#include
#include
#include
#include
#include
#include
#include
#include 
#include 
#include
#include
using namespace std;
#define INF 1e8
#define eps 1e-8
#define LL long long
#define maxn 127
#define PI acos(-1.0)

struct node
{
	int v,p;
}f[11][10005];
int main()
{
	int n,m,k;
	int dp[11][10005];
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		int i,j;
		int a,b,c;
		int kao[15];
		memset(kao,0,sizeof(kao));
		memset(f,0,sizeof(f));
		for(i=0;i=f[i][h].p;j--)
				{
					if(dp[i][j-f[i][h].p]!=-1)//由当前状态转移
						dp[i][j]=max(dp[i][j],dp[i][j-f[i][h].p]+f[i][h].v);

					if(dp[i-1][j-f[i][h].p]!=-1)//由上一状态转移
						dp[i][j]=max(dp[i][j],dp[i-1][j-f[i][h].p]+f[i][h].v);
				}
			}
		}
		if(dp[k][m]==-1) printf("Impossible\n");
		else 
			printf("%d\n",dp[k][m]);
	}
	return 0;
}
/*
5 10 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66
*/


点击复制链接 与好友分享!回本站首页
相关TAG标签 背包
上一篇:C++ Primer Plus学习笔记之继承类的初始化顺序
下一篇:UVA - 11525 Permutation
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站