频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
Hdu 3033 I love sneakers!(DP_背包)
2012-05-28 11:06:48           
收藏   我要投稿

题目大意:xx去买鞋,有k种牌子,然后给出n双鞋,每双鞋有它属于的牌子、价格、收藏价值。xx认为他不差钱,要求每种鞋子买一双。但实际上他只有m毛钱,问能否买到符合xx要求的鞋,能找到的话输出最大的收藏价值总和。

解题思路:分组背包的变形,每种牌子要求至少选一个,这与分组的最多选一个不一样,但背包的思想都是一样的。状态转移的时候可以从上一组转移(选择1个)与本组转移(大于1个)。
    状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-cost[i][k]] + val[i][k],dp[i][j-cost[[\i][k]] + val[i][k]) (dp[i][j]表示选到i组填到容量j的最大价值,cost[i][k]表示第i组第k组的花费,val同上)

测试数据:
 5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66


3 10000 2
1 2 3
1 3 4
1 5 6


5 10000 3
1 1000 3
1 1000 4
2 100000 4
3 1000 3
3 1000 4

代码:
[cpp]
#include <iostream> 
#include <string.h> 
using namespace std; 
#define MAX 11000 
 
struct node 

    int cos,val; 
}arr[11][MAX]; 
int dp[11][MAX],len[11]; 
 
 
int max(int a,int b){ 
 
    return a > b ? a : b;  

 
 
int main() 

    int i,j,k,t,n,m; 
    int a,b,c,tot,ans,s; 
 
 
    while (scanf("%d%d%d",&n,&m,&k) != EOF){ 
 
        memset(len,0,sizeof(len)); 
        memset(dp,-1,sizeof(dp)); 
        for (i = 1; i <= n; ++i){ 
 
            scanf("%d%d%d",&a,&b,&c); 
            len[a]++; 
            arr[a][len[a]].cos = b; 
            arr[a][len[a]].val = c; 
        } 
 
 
        tot = dp[0][0] = 0; 
        for (i = 1; i <= k; ++i) { 
 
            if (!len[i]) break; 
            tot++; 
 
 
            for (j = 1; j <= len[i]; ++j) 
                for (s = m; s >= arr[i][j].cos; --s) { 
 
                    if (dp[tot][s-arr[i][j].cos] != -1) { 
 
                        int tp = dp[tot][s-arr[i][j].cos] + arr[i][j].val; 
                        dp[tot][s] = max(dp[tot][s],tp); 
                    } 
 
 
                    if (dp[tot-1][s-arr[i][j].cos] != -1) { 
 
                        int tp = dp[tot-1][s-arr[i][j].cos] + arr[i][j].val; 
                        dp[tot][s] = max(dp[tot][s],tp); 
                    } 
                }//for s 
        }//for i 
 
 
        for (ans = -1,i = m; i >= 0; --i) 
            if (ans < dp[tot][i]) ans = dp[tot][i]; 
        if (tot == k && ans != -1) cout<<ans<<endl; 
        else cout<<"Impossible"<<endl; 
    } 

 


摘自 ZeroClock

点击复制链接 与好友分享!回本站首页
相关TAG标签 背包
上一篇:Hdu 3535 AreYouBusy(DP_背包)
下一篇:Hdu 1712 ACboy needs your help(DP_背包)
相关文章
图文推荐
点击排行

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

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