題目鏈接: acm.hdu.edu.cn/showproblem.php?pid=1712
分析: 這是一個(gè)01背包的變體 ,但始終是01背包,只不過(guò), 每 個(gè)物體的代價(jià)和 利益的狀態(tài)不唯一(也就是說(shuō)花費(fèi)不同的代價(jià) 得到不同的利益 ) . 所以只要在最里面再加一 層循環(huán),遍歷 每個(gè)物體的不代價(jià)和利益的狀態(tài) 即可!
?
#include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<cctype> #include<iomanip> using namespace std; const int maxn=100000; int map[105][105]; int dp[102]; int main(){ int n,m; while(cin>>n>>m,n||m){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>map[i][j]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;++i) for(int k=m;k>=1;--k) for(int j=1;j<=k;++j){ if(dp[k]<dp[k-j]+map[i][j]) dp[k]=dp[k-j]+map[i][j]; } cout<<dp[m]<<endl; } return 0; }
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
