概述
嗯……背包問題是什麼？
背包問題，是動态規劃問題中的典型的一類。顧名思義，是跟背包有關的問題（竟然和名字有關，爺青結）。
大概就是講背包空間有限，怎樣合理地裝物品可以讓總價值最高的問題。
其實也不是非常難。
本文講哪幾類？
背包問題的主要難點也就在于種類繁多，需要記憶各種遞推公式、循環結構。
不過畢竟是記憶而已，總是比其他需要現場推倒遞推公式的要好不少。
本文主要講以下幾類：
01背包問題
完全背包問題（目前隻講前兩種，後面的以後慢慢更新，畢竟所有背包都是以這兩種為基礎的）（後面的題目已經寫好，以後講解）
多重背包問題
二維費用背包問題
分組背包問題
01背包問題
題目
題目描述
一個旅行者有一個最多能裝 MM 公斤的背包，現在有 nn 件物品，它們的重量分别是W1，W2，...,WnW1，W2，...,Wn,它們的價值分别為C1,C2,...,CnC1,C2,...,Cn，求旅行者能獲得最大總價值。
輸入
第一行：兩個整數，MM(背包容量，M≤200M≤200)和NN(物品數量，N≤30N≤30)；
第2..N+12..N+1行：每行二個整數Wi，CiWi，Ci，表示每個物品的重量和價值。
輸出
僅一行，一個數，表示最大總價值。
輸入樣例
10 4
2 1
3 3
4 5
7 9 輸出樣例
12 講解
既然要用用動态規劃法解決0-1背包問題，我們就先定義動态規劃的三個要點，即狀态、狀态轉移方程和邊界條件。
首先我們用子問題定義狀态，我們用F(i,j)表示“把前i件物品放入容量為j的背包中的最大總重量”。
然後我們要考慮怎樣的狀态轉移方程可以把這個問題轉化為更小的子問題。我們依然以“每一個物品都有放或不放兩種選擇”的政策為基礎，考慮第i件物品，如果我們選擇不放第i件物品，那麼問題就直接轉化為“把前i-1件物品放入容量為j的背包中的最大總重量”，如果我們選擇放第i件物品，那麼問題就轉化為“把前i-1件物品放入容量為j-V[i]的背包中的最大總重量加上第i件物品的重量”（這裡值得注意的一點是，如果j-V[i]<0，即放入第i件物品後超過了背包容量的限制，那麼我們就隻能選擇不放第i件物品了）。是以狀态轉移方程為F(i,j)=max{F(i-1,j),F(i-1,j-V[i])+W[i]}。
邊界條件則很容易得到，i=0時F(i,j)為0（沒有物品就沒有重量），j<0時F(i,j)為負無窮（但在代碼中并不會這樣初始化，我們在j-V[i]<0時不計算第二種情況即可）。最終答案則是f(n,C)。
但其實這個空間複雜度是可以優化的。
可以直接用f[i]來表示當重量為i時，可以有的最大價值。
狀态轉移方程：
f[j] = max(f[j], f[j-c[i]]+w[i]) 到了這裡，終于要講循環順序的問題了。
其實第二層循環為什麼要反向的問題，我也研究了好久，終于在看一篇文章的時候恍然大悟。
根據題意，每種物品隻有一件。
當我們循環的時候，如果正序，那自然就會從前到後的更新數組。
那如果背包容量大于某件物品的多倍呢？
而恰好這件物品成本效益很高？
假設a是一個常數。這件物品的品質為w。
那麼，比如說，我們在循環到i=a的時候，把這件物品裝進了背包。
那再循環到i=a+w的時候，可能又會把這件物品裝進背包。
也就是說，這件物品被使用了兩次，甚至後面可能更多。
而根據題意，每件物品隻有一個。
而對于每一次更新，隻會用到i比目前小的資料，而不會用到i比目前大的。（因為要檢視f[i-w[j]],w[j]不可能是負的）
是以，先把大的更新了是沒有問題的。
（學了背包問題這麼久，終于把這個問題解決了！！！開心！！！）
核心代碼：
#include <iostream>
#include <cstdio>
#define M 1000
using namespace std;
int f[M], c[M], w[M];
int ans, v, m;
int main()
{
scanf("%d%d", &v, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= m; i++)
{
for(int j = v; j >= c[i]; j--)
{
f[j] = max(f[j], f[j-c[i]]+w[i]);
}
}
printf("%d\n", f[v]);
return 0;
} 完全背包問題
題目
題目描述
設有nn種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為MM，今從nn種物品中選取若幹件(同一種物品可以多次選取)，使其重量的和小于等于MM，而價值的和為最大。
輸入
第一行：兩個整數，MM(背包容量，M≤200M≤200)和NN(物品數量，N≤30N≤30)；
第2..N+12..N+1行：每行二個整數Wi,CiWi,Ci，表示每個物品的重量和價值。
輸出
僅一行，一個數，表示最大總價值。
輸入樣例
10 4
2 1
3 3
4 5
7 9 輸出樣例
max=12 講解
那麼，既然剛才講了01背包因為每種物品隻有一個是以隻能逆序循環，完全背包問題自然就是把循環順序改為順序就可以了！
——就這？就這？就這？
——對，就這。
——啊這，淚目
[doge]
核心代碼
#include <iostream>
#include <cstdio>
#define M 1000
using namespace std;
int f[M], c[M], w[M];
int ans, v, m;
int main()
{
scanf("%d%d", &v, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= m; i++)
{
for(int j = c[i]; j <= v; j++)
{
f[j] = max(f[j], f[j-c[i]]+w[i]);
}
}
printf("max=%d\n", f[v]);
return 0;
} 多重背包問題
題目
題目描述
為了慶賀班級在校運動會上取得全校第一名成績，班主任決定開一場慶功會，為此撥款購買獎品犒勞運動員。期望撥款金額能購買最大價值的獎品，可以補充他們的精力和體力。
輸入
第一行二個數n(n≤500)，m(m≤6000)，其中n代表希望購買的獎品的種數，m表示撥款金額。
接下來n行，每行3個數，v、w、s，分别表示第I種獎品的價格、價值（價格與價值是不同的概念）和能購買的最大數量（買0件到s件均可），其中v≤100，w≤1000，s≤10。
輸出
一行：一個數，表示此次購買能獲得的最大的價值（注意！不是價格）。
輸入樣例
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1 輸出樣例
1040
講解
其實多重背包問題，雖然一個物品有了好幾個，但是仍然可以按照01背包問題的思路，每個物品能取幾件就存儲幾次就好了（當做不同的物品）
核心代碼
#include <bits/stdc++.h>
#define M 1000
using namespace std;
int f[M], c[M], w[M],num[M];
int ans, v, m;
int main()
{
scanf("%d%d", &v, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &c[i], &w[i],&num[i]);
}
int jjc=m;
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= num[i]; ++j)
{
c[jjc]=c[i];
w[jjc]=w[i];
jjc++;
}
}
for(int i = 1; i <= m; i++)
{
for(int j = c[i]; j <= v; j++)
{
f[j] = max(f[j], f[j-c[i]]+w[i]);
}
}
printf("max=%d\n", f[v]);
return 0;
} 二維費用背包問題
題目描述
寵物小精靈是一部講述小智和他的搭檔皮卡丘一起冒險的故事。
一天，小智和皮卡丘來到了小精靈狩獵場，裡面有很多珍貴的野生寵物小精靈。小智也想收服其中的一些小精靈。然而，野生的小精靈并不那麼容易被收服。對于每一個野生小精靈而言，小智可能需要使用很多個精靈球才能收服它，而在收服過程中，野生小精靈也會對皮卡丘造成一定的傷害（進而減少皮卡丘的體力）。當皮卡丘的體力小于等于0時，小智就必須結束狩獵（因為他需要給皮卡丘療傷），而使得皮卡丘體力小于等于0的野生小精靈也不會被小智收服。當小智的精靈球用完時，狩獵也宣告結束。
我們假設小智遇到野生小精靈時有兩個選擇：收服它，或者離開它。如果小智選擇了收服，那麼一定會扔出能夠收服該小精靈的精靈球，而皮卡丘也一定會受到相應的傷害；如果選擇離開它，那麼小智不會損失精靈球，皮卡丘也不會損失體力。
小智的目标有兩個：主要目标是收服盡可能多的野生小精靈；如果可以收服的小精靈數量一樣，小智希望皮卡丘受到的傷害越小（剩餘體力越大），因為他們還要繼續冒險。
現在已知小智的精靈球數量和皮卡丘的初始體力，已知每一個小精靈需要的用于收服的精靈球數目和它在被收服過程中會對皮卡丘造成的傷害數目。請問，小智該如何選擇收服哪些小精靈以達到他的目标呢？
輸入
輸入資料的第一行包含三個整數：N(0<N<1000)，M(0<M<500)，K(0<K<100)，分别代表小智的精靈球數量、皮卡丘初始的體力值、野生小精靈的數量。
之後的K行，每一行代表一個野生小精靈，包括兩個整數：收服該小精靈需要的精靈球的數量，以及收服過程中對皮卡丘造成的傷害。
輸出
輸出為一行，包含兩個整數：C，R，分别表示最多收服C個小精靈，以及收服C個小精靈時皮卡丘的剩餘體力值最多為R。
輸入樣例#01
10 100 5
7 10
2 40
2 50
1 20
4 20 輸出樣例#01
3 30 輸入樣例#02
10 100 5
8 110
12 10
20 10
5 200
1 110 輸出樣例#02
0 100 提示
對于樣例輸入1：小智選擇：(7,10) (2,40) (1,20) 這樣小智一共收服了3個小精靈，皮卡丘受到了70點傷害，剩餘100-70=30點體力。是以輸出3 30。
對于樣例輸入2：小智一個小精靈都沒法收服，皮卡丘也不會收到任何傷害，是以輸出0 100。
分組背包問題
題目
題目描述
一個旅行者有一個最多能裝V公斤的背包，現在有n件物品，它們的重量分别是W1，W2，...,WnW1，W2，...,Wn，它們的價值分别為C1,C2,...,CnC1,C2,...,Cn。這些物品被劃分為若幹組，每組中的物品互相沖突，最多選一件。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
輸入
第一行：三個整數，V(背包容量，V≤200)，N(物品數量，N≤30)和T(最大組号，T≤10)；
第2..N+1行：每行三個整數Wi,Ci,PWi,Ci,P，表示每個物品的重量，價值，所屬組号。
輸出
僅一行，一個數，表示最大總價值。
輸入樣例
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3 輸出樣例
20