欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

動態(tài)規(guī)劃——二維費用的背包問題-創(chuàng)新互聯(lián)

二維費用背包問題：

背包的限制條件有兩個，此時我們直接加上一重循環(huán)即可。注意二維限制可以加在任意類型的背包問題上。

創(chuàng)新互聯(lián)服務(wù)項目包括南平網(wǎng)站建設(shè)、南平網(wǎng)站制作、南平網(wǎng)頁制作以及南平網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，南平網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到南平省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

例題：

有?N?件物品和一個容量是?V 的背包，背包能承受的大重量是?M。

每件物品只能用一次。體積是?vi，重量是?mi，價值是?wi。

輸出大價值。

輸入格式：

第一行三個整數(shù)，N,V,M，用空格隔開，分別表示物品件數(shù)、背包容積和背包可承受的大重量。

接下來有?N?行，每行三個整數(shù)?vi,mi,wi，用空格隔開，分別表示第?i 件物品的體積、重量和價值。

輸出格式：

輸出一個整數(shù)，表示大價值。

思路：

該題為二維費用的01背包。f[i][j][k]表示前i個物品，背包體積為j，承重為k的時候的大價值。在01背包基礎(chǔ)上加上一重循環(huán)即可。由于n*3的空間太大，所以我們直接使用優(yōu)化后的01背包。

代碼如下：

#includeusing namespace std;

int f[1010][1010];
int N, V, M;

int main() {
    cin >>N >>V >>M;

    int v, m, w;
    for (int i = 0; i< N; i++) {
        cin >>v >>m >>w;
        for (int j = V; j >= v; j--)
            for (int k = M; k >= m; k--)
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }

    cout<< f[V][M];

    return 0;

}
例題： 寵物小精靈之收服：

小智想收服一些小精靈。

對于每一個野生小精靈而言，小智可能需要使用很多個精靈球才能收服它，而在收服過程中，野生小精靈也會對皮卡丘造成一定的傷害。

當(dāng)皮卡丘的體力小于等于0或者精靈球用完時，小智就必須結(jié)束狩獵。

小智的目標(biāo)有兩個：主要目標(biāo)是收服盡可能多的野生小精靈；如果可以收服的小精靈數(shù)量一樣，小智希望皮卡丘受到的傷害越小。

輸入格式：

輸入數(shù)據(jù)的第一行包含三個整數(shù)：N，M，K，分別代表小智的精靈球數(shù)量、皮卡丘初始的體力值、野生小精靈的數(shù)量。

輸出格式：

輸出為一行，包含兩個整數(shù)：C，R，分別表示最多收服C個小精靈，以及收服C個小精靈時皮卡丘的剩余體力值最多為R。

二維的01背包問題，像普通01背包一樣做就行，只是加一層循環(huán)。最后輸出f[n][m]（n個球，m個體力）。要輸出剩下的體力值，我們遍歷f[n][0]~f[n][m]即可。

題目要求當(dāng)體力為0的時候算抓捕失敗，所以我們把m-1當(dāng)做m帶入計算即可。

代碼如下：

#includeusing namespace std;
const int N=1010;
int f[N][N];
int n,m,k;//擁有的球數(shù)和體力值、精靈數(shù)
int main(){
    cin>>n>>m>>k;
    int a,b;//每只精靈需要的球數(shù)和照成的傷害
    for(int i=0;i>a>>b;
        for(int j=n;j>=a;j--)//遍歷球數(shù)
            for(int u=m-1;u>=b;u--)//遍歷體力
                f[j][u]=max(f[j][u],f[j-a][u-b]+1);
    }
    
    int tmp=0;
    for(int i=m;i>=0;i--)
        if(f[n][i]==f[n][m-1])tmp=i;
        
    cout<
潛水員：

潛水員為了潛水要使用特殊的裝備。

他有一個帶2種氣體的氣缸：一個為氧氣，一個為氮氣。

每個氣缸都有重量和氣體容量。

他完成工作所需氣缸的總重的最低限度的是多少？

輸入格式：

第一行有2個整數(shù)?m，n。它們表示氧，氮各自需要的量。

第二行為整數(shù)?k?表示氣缸的個數(shù)。

此后的?k?行，每行包括ai，bi，ci，3個整數(shù)。這些各自是：第?i?個氣缸里的氧和氮的容量及氣缸重量。

輸出格式：

僅一行包含一個整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值。

二維費用的01背包問題。f[i][j][k]代表只看前i個氣缸，氧氣至少為j，氮氣至少為k時的大重量（注意氧氣和氮氣可以多）。

選第i個：

f[i][j][k] = f[i - 1][j - o2[i]][k - n2[i]]

不選第i個：

f[i][j][k] = f[i - 1][j][k]。

本題要求的是最小值， 每個狀態(tài)為了不被0影響，需要把所有狀態(tài)更新為INF，特別的，f[0][0][0]=0。

由于是最少需要的氧氣和氮氣，所以氮氣和氧氣超出了也是可以的。相當(dāng)于背包容量不夠了也是可以裝當(dāng)前這個物品的。在更新的時候需要額外更新一些狀態(tài)。比如我們只需要5的氧氣，但是當(dāng)前物品的氧氣為8，我們也是可以選擇的，f[i][5][j]=f[i-1][0][j]+w。

代碼如下：

#include#includeusing namespace std;

const int N = 1010;
int f[N][N];//o2,n2
int n, m;//o2,n2

int main() {
    cin >>n >>m;
    int s, o2, n2, m2;
    cin >>s;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i< s; i++) {
        cin >>o2 >>n2 >>m2;
        for (int j = n; j >= 0; j--)
            for (int k = m; k >= 0; k--)
                f[j][k] = min(f[j][k], f[max(j - o2, 0)][max(k - n2, 0)] + m2);
    }

    cout<< f[n][m];

    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：動態(tài)規(guī)劃——二維費用的背包問題-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://www.chinadenli.net/article18/dcihgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、移動網(wǎng)站建設(shè)、網(wǎng)站改版、定制開發(fā)、網(wǎng)站收錄、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)