您當前位置：首頁 > 互聯網 > HDU 1712 ACboy needs your help(分組背包)

HDU 1712 ACboy needs your help(分組背包)

來源：程序員人生發布時間：2014-11-11 08:13:26 閱讀次數：2553次

http://acm.hdu.edu.cn/showproblem.php?pid=1712

題意:

小杰有m天的時間去上n門不同的課. 對第i門課來講, 如果小杰花j天的時間在該課上, 那末小杰可以取得val[i][j]的價值. 現在給出矩陣val[n][m], 要你求出小杰能取得的最大價值和?

分析:

咋1看, n門課, m天的時間, 要我們求最大價值. 那末明顯是從n門課當選出適合的幾門, 是的總花費的時間<=m的條件下, 價值最大化. 但是發現每門課有m種不同的價值獲得方式.

所以我們換1種問題描寫方式: 有n組物品, 每組物品有m個且每組物品中最多只能選1個物品. 第i組物品的花費分別為1 2 3 …m, 第i組物品的價值分別為val[i][1], val[i][2]…val[i][m]. 現在問你初始金錢為m時, 通過上面n組物品, 最多能取得多少價值的物品?

上面問題就是1個明顯的分組背包問題了. 我們令dp[i][j]==x表示只選前i組物品且總花費<=j時, 能取得的最大價值為x.

初始化: dp全為0.

狀態轉移: dp[i][j] == max( dp[i⑴][j] , dp[i⑴][j-cost[k]]+val[k])

其中cost[k]和val[k]指的是第i組物品的第k個物品的花費和價值.

上面公式前者表示第i組物品1個都不選, 后者表示第i組物品選1個.

終究所求: dp[n][m]的值.

注意: dp遞推的3層循環的相互順序不能改變, 否者會錯.(可以自己想想為何是這樣的循環順序).程序用的轉動數組, dp只有1維.

AC代碼:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; int n;//n組物品 int m;//初始金錢數和每組中物品數目 int cost[maxn][maxn]; int val[maxn][maxn]; int dp[maxn]; int main() { while(scanf("%d%d",&n,&m)==2 && n) { //讀取輸入 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&val[i][j]); cost[i][j]=j; } //遞推進程 memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++)//第i組 for(int j=m;j>=0;j--)//<=j花費時 for(int k=1;k<=m;k++)//第i組的第k個物品 { if(j>=cost[i][k]) dp[j] = max(dp[j], dp[j-cost[i][k]]+val[i][k]); } //輸出結果 printf("%d ",dp[m]); } return 0; }

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 【十四】注入框架RoboGuice使用總結

下一篇 Webx框架：依賴注入

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

HDU 1712 ACboy needs your help(分組背包)