频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 3033 I love sneakers!(分组背包,每组至少取一件)
2014-05-05 11:32:35         来源:hdu 3033 I love sneakers!(分组背包,每组至少取一件)  
收藏   我要投稿

 

大致题意:某人要买鞋子,有k种鞋,要求每种鞋至少买一双,给出每双鞋子的花费和价值,问m元钱可以买到的鞋子的最大价值是多少。

 

思路:分组背包问题。与传统的分组背包不同:每组物品至少取一件;且每组中物品任意取。

 

想一想传统的分组背包,每组至多选一件:

for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}
这里需要每组至少选一个,需要对每组中的物品进行01背包,即该物品在该组中要么被选要么不被选。实现这一目的,只需要将第二个循环与第三个循环交换一下即可。

具体解法:设dp[i][j]表示到第i组为止j元钱能够获得的最大价值。
dp[i][j] = Max(dp[i][j],dp[i][j-item[i][k].cost]+item[i][k].val, dp[i-1][j-item[i][k].cost]+item[i][k].val)。
初始化所有的dp[i][j] = -1,表示所有的都不合法,是为了保证每组物品能够至少取一件;dp[0][0-m] = 0为了使第一组能够合法计算。


#include  #include  #include  #include#include  #include  #include  #include  #define LL long long #define _LL __int64 using namespace std; struct node { int cost,val; }item[12][110]; int dp[12][10010]; int num[12]; int n,m,k; void solve() { //注意初始化 memset(dp,-1,sizeof(dp)); //全部初始化为不合法 for(int i = 0; i <= m; i++) //第0组初始化为合法,以便计算第一组 dp[0][i] = 0; for(int i = 1; i <= k; i++) { for(int j = 0; j < num[i]; j++) { for(int g = m; g >= item[i][j].cost; g--) { //注意两个判断条件的顺序 if( dp[i][g-item[i][j].cost] != -1 ) dp[i][g] = max( dp[i][g], dp[i][g-item[i][j].cost]+item[i][j].val); if( dp[i-1][g-item[i][j].cost] != -1 ) dp[i][g] = max( dp[i][g], dp[i-1][g-item[i][j].cost]+item[i][j].val); } } } } int main() { while(~scanf(%d %d %d,&n,&m,&k)) { memset(num,0,sizeof(num)); int a,b,c; for(int i = 0; i < n; i++) { scanf(%d %d %d,&a,&b,&c); item[a][num[a]].cost = b; item[a][num[a]].val = c; num[a]++; } solve(); if(dp[k][m] < 0) printf(Impossible ); else printf(%d ,dp[k][m]); } return 0; } 




 

点击复制链接 与好友分享!回本站首页
相关TAG标签 背包
上一篇:uva10106 - Product
下一篇:hdu 4725 The Shortest Path in Nya Graph(dijkstra+优先队列)
相关文章
图文推荐
点击排行

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

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