欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

01背包問(wèn)題

題目描述: ( 轉自背包九講1 )

有N件物品和一個(gè)容量為V的背包。第i件物品的費用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

基本思路
這是最基礎的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。

用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v]；如果放第i件物品，那么問(wèn)題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。

我的理解:

狀態(tài)轉移方程很好理解,我們想你的包是固定大小的,而一堆東西在外面,我們可以選擇放當前拿到手的物品,那包的體積肯定要減小,如果我們不放這個(gè)物品,那背包里的物品價(jià)值和容量當然保持不變了.

我喜歡設狀態(tài)數組為DP[i][v];

那么下標分別是什么意思呢? 我們可以將 i 當成物品的編號,把v當成當前背包的體積

PKU ACM 有道原題鏈接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3624

題目大意:

給定一個(gè)背包的物品數量和背包體積,然后分別輸入每個(gè)物品的體積和價(jià)值
最后輸出背包裝滿(mǎn)后最大價(jià)值量

樣例輸入:
4 6
1 4
2 6
3 12
2 7
樣例輸出:
23

我們輸出DP數組看一下:
  1  2  3  4  5  6
1 4  4  4  4  4  4
2 4  6  10 10 10 10
3 4  6  12 16 18 22
4 4  7  12 16 19 23

最上一排和最左一排是行下標和列下標,我們看到 DP[1][1] 代表什么呢? 代表有第1個(gè)物品,并且當前背包體積為1的時(shí)候最大的量,當然是4了,而DP[2][2]呢? 代表當前放入物品2,因為當前體積為2,而物品2體積就是2了,所以1就不能放了,好,DP[2][2] = 6,同理,DP[4][6] 就代表體積裝滿(mǎn)的時(shí)候,背包里面的總價(jià)值,為23.

這里時(shí)間復雜度不能優(yōu)化了,而我們可以?xún)?yōu)化空間復雜度,我們觀(guān)察DP數組的最后一行:
先考慮上面講的基本思路如何實(shí)現，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來(lái)二維數組f[i][0..V]的所有值。那么，如果只用一個(gè)數組f [0..V]，能不能保證第i次循環(huán)結束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個(gè)子問(wèn)題遞推而來(lái)，能否保證在推f[i][v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[v-c[i]]保存的是狀態(tài)f[i -1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因為現在的f[v-c[i]]就相當于原來(lái)的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話(huà)，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個(gè)重要的背包問(wèn)題P02最簡(jiǎn)捷的解決方案，故學(xué)習只用一維數組解01背包問(wèn)題是十分必要的。
核心程序:
for ( int i = 1; i <= N; i++ )
{
 for ( int v = V; v>=1; --v )
 {
  if ( v >= cost[i] )
  {
   if ( DP[v-cost[i]] + value[i] >= DP[v] ) {
                         DP[v] = DP[v-cost[i]] + value[i];      
              }
}
 //DP[v-cost[i]]+value[i]就是說(shuō)目前包里要裝第i個(gè)物品
//看看裝第i個(gè)物品和不裝它哪個(gè)大,第一次開(kāi)始時(shí)DP[6],就是說(shuō)可以裝
//單位重量的物品,然后依次類(lèi)推,5,4,3,2,1,看看有或沒(méi)有第i個(gè)物品的總價(jià)值

C++ 代碼:

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
 vector<int> value;
 vector<int> volume;
 vector<int> DP;
 int N,V;
 while ( cin >> N >> V )
 {
  value.resize(N+1);
  volume.resize(V+1);
  DP.clear();
  DP.resize(V+1);
  for ( int i = 1; i <= N; i++ )
  {
   cin >> volume[i] >> value[i];
  }
  for ( int i = 1; i <= N; i++ )
  {
   for ( int v = V; v >= 1; v-- )
   {
    if ( v >= volume[i] )
    {
     if ( DP[v-volume[i]] + value[i] >= DP[v] )
     {
      DP[v] = DP[v-volume[i]] + value[i];
     }
    }
   }
  }
  cout << DP[V] << endl;
 }
 return 0;
}