0/1背包是最基本的背包問題，其基本特點是：每種物品僅有一件，可以選擇放或不放，即每個物品最多只能放一次，
0/1背包問題的一般描述為：有N個物品，第i個物品的重量與價值分別為W[i]與P[i]，背包容量為V，試問在每個物品最多使用一次（物品必須保持完整）的情況下，如何讓背包裝入的物品具有更大的價值總和，
其一般解題思路為：
設f[i][j]表示容量為j時放入前i個物品得到的最大價值，
對于第i件物品，有兩種選擇，即放或者不放，
如果不放，則f[i][j]=f[i-1][j]；
如果放，則f[i][j]=f[i-1][j-W[i]]+P[i]
因此有狀態轉移方程：f[i][j]=max (f[i-1][j], f[i-1][j-W[i]]+P[i])，
撰寫代碼時，一般可以寫成如下的回圈，
for (i=1;i<=N;i++) // 對每件物品進行處理
for (j=1;j<=V;j++)
{
if (j-W[i]<0)
f[i][j]=f[i-1][j];
else
{
f[i][j]=max(f[i-1][j],f[i-1][j-W[i]]+P[i]);
}
}
最優值為f[N][V]，
由上面的回圈程序可知，回圈程序中的f[i][j]僅與f[i-1][j]或f[i-1][j-W[i]]相關，因此可以將存盤空間由二維陣列壓縮成一維陣列，即
f[j]=max（f[j], f[j?W[i]]+P[i]）
在具體遞推處理時，需要采用逆推的方法進行計算最優值，一般寫成如下的回圈，
for (i=1;i<=N;i++) // 對每件物品進行處理
for (j=V;j>=W[i];j--) // 逆推計算最優值
{
f[j]=max(f[j],f[j-W[i]]+P[i]);
}
對于背包問題，陣列f的初始化也需要注意，對于不同的問題，初始化值一般不同，
一般在求最優解的背包問題題目中，有兩種不太相同的問法，有的題目要求“恰好裝滿背包”時的最優解，有的題目則并沒有要求必須把背包裝滿，這兩種問法的實作方法在初始化的時候就有所不同，
如果是要求“恰好裝滿背包”，那么在初始化時，除了f[0]為0，其它元素f[1]~f[V]均初始化為-∞，這樣就可以保證最終得到的f[V]是一種恰好裝滿背包的最優解，
如果并沒有要求必須把背包裝滿，而是只希望獲得的價值盡量大，初始化時應該將f[0]~f[V]全部設為0，
為什么要這樣初始化呢？
初始化f陣列事實上就是在沒有任何物品放入背包時的合法狀態，如果要求背包“恰好裝滿”，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態，它們的值就都應該是-∞了，如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時f的值也就全部為0了，
0/1背包問題是最基本的背包問題，它包含了背包問題中設計狀態、確定狀態轉移方程的最基本思想，另外，其他型別的背包問題往往也可以轉換成0/1背包問題求解，因此需要認真體會并掌握，
【例1】采藥
問題描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師，為此，他想拜附近最有威望的醫師為師，醫師為了判斷他的資質，給他出了一個難題，醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值，我會給你一段時間，在這段時間里，你可以采到一些草藥，如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大，”
如果你是辰辰，你能完成這個任務嗎？
輸入
第一行有2個整數 T（1≤T≤1000）和M（1≤M≤100），用一個空格隔開，T代表總共能夠用來采藥的時間，M 代表山洞里的草藥的數目，
接下來的 M行每行包括兩個在1到 100 之間（包括 1和100）的整數，分別表示采摘某株草藥的時間和這株草藥的價值，
輸出
輸出在規定的時間內可以采到的草藥的最大總價值，
輸入樣例
70 3
71 100
69 1
1 2
輸出樣例
3
（1）編程思路，
這是一道典型的0/1背包問題，把采摘每株草藥的時間看做標準模型中的重量，把規定的時間看做載重為T的背包，這樣問題和基本模型就一樣了，
分別采用二維陣列和一維陣列的方法撰寫源程式如下，
（2）采用二維陣列撰寫的源程式1，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int f[101][1001]={0}; int w[101],v[101]; int t,m; scanf("%d%d",&t,&m); int i,j; for (i=1;i<=m;i++) { scanf("%d%d",&w[i],&v[i]); } for (i=1;i<=m;i++) for (j=1;j<=t;j++) { if (j-w[i]<0) f[i][j]=f[i-1][j]; else { f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); } } printf("%d\n",f[m][t]); return 0; }
（3）采用一維陣列撰寫的源程式2，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int f[1001]={0}; int w[101],v[101]; int t,m; scanf("%d%d",&t,&m); int i,j; for (i=1;i<=m;i++) { scanf("%d%d",&w[i],&v[i]); } for (i=1;i<=m;i++) for (j=t;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+v[i]); } printf("%d\n",f[t]); return 0; }
將上面的源程式提交給洛谷題庫P1048 [NOIP2005 普及組] 采藥（https://www.luogu.com.cn/problem/P1048），測評結果為“Accepted”，
【例2】背包問題
問題描述
有N件物品和一個容量為M的背包，第i件物品的重量是Wi，價值是Di，求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大，
輸入
第一行：物品個數N （1≤N≤3,402）和背包大小M（1≤M≤12,880），
第二行至第 N+1 行：第i 個物品的重量 Wi（1≤Wi≤400）和價值Di（1≤Di≤100），
輸出
輸出一行最大價值，
輸入樣例
4 6
1 4
2 6
3 12
2 7
輸出樣例
23
（1）編程思路，
最基本的0/1背包問題，可以按前面介紹的模板寫成一維陣列的方式，也可以寫成二維陣列的方式，
（2）采用一維陣列撰寫的源程式1，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int f[12881]={0}; int n,m; scanf("%d%d",&n,&m); int c[3500],w[3500]; int i,j; for (i=1;i<=n;i++) { scanf("%d%d",&c[i],&w[i]); } for (i=1;i<=n;i++) for (j=m;j>=c[i];j--) { f[j]=max(f[j],f[j-c[i]]+w[i]); } printf("%d\n",f[m]); return 0; }
將上面的源程式1提交給洛谷題庫P2871 [USACO07DEC]Charm Bracelet S（https://www.luogu.com.cn/problem/P2871），測評結果為“Accepted”，
（3）采用二維陣列撰寫的源程式2，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int f[3410][12881]={0}; int main() { int n,m; scanf("%d%d",&n,&m); int d[3410],w[3410]; int i,j; for (i=1;i<=n;i++) { scanf("%d%d",&w[i],&d[i]); } for (i=1;i<=n;i++) // 對每件物品進行處理 for (j=1;j<=m;j++) { if (j-w[i]<0) f[i][j]=f[i-1][j]; else { f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+d[i]); } } printf("%d\n",f[n][m]); return 0; }
將上面的源程式2提交給洛谷題庫P2871 [USACO07DEC]Charm Bracelet S（https://www.luogu.com.cn/problem/P2871），測評結果為“Unaccepted”，其中測驗點#2和測驗點#10，顯示“MLE”，
【例3】裝箱問題
題目描述
有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30，每個物品有一個體積（正整數），
要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小，
輸入格式
1個整數，表示箱子容量
1個整數，表示有n個物品
接下來n行，分別表示這n個物品的各自體積，
輸出格式
1個整數，表示箱子剩余空間，
輸入樣例
24
6
8
3
12
7
9
7
輸出樣例
0
（1）編程思路1，
本題也是典型的0/1背包問題，并且是0/1背包的簡化版，把箱子看成背包，容量看成載重量，每個物品的體積看成重量，剩余空間最小也就是盡量裝滿背包，于是這個問題便成了：
有一個載重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重，
定義陣列f[20001]，其中元素f[i]表示重量i可否構成，
狀態轉移方程為： f[j]=f[j-w[i]] { f[j-w[i]]=true}
初始時，f[0]=1，什么也不裝，重量0肯定可以構成，其余元素全部為0，
最終的解就是v-x （x<=n 且f[x]=true 且 f[x+1..n]=false），
（2）源程式1，
#include <stdio.h> int main() { int f[20001]={0}; int v,n; scanf("%d%d",&v,&n); int w[31]; int i,j; for (i=1;i<=n;i++) { scanf("%d",&w[i]); } f[0]=1; for (i=1;i<=n;i++) for (j=v;j>=w[i];j--) { if (f[j-w[i]]==1) f[j]=1; } for (i=v;i>0;i--) if (f[i]==1) break; printf("%d\n",v-i); return 0; }
（3）編程思路2，
也可以這樣解決問題，
定義陣列f[20001]，其中元素f[j]表示載重量為j的背包可裝載的最大重量，
顯然對于每個物品i而言，
要么不裝，f[j]=f[j]，
要么裝， f[j]=f[j-w[i]]+w[i]
取二者的較大值，
因此，狀態轉移方程為：f[j]=max(f[j],f[j-w[i]]+w[i])
這個狀態轉移方程可以這樣理解：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大時，就裝上它，
初始時，陣列f的元素值全部為0，各背包全部為空，
最終的解就是v-f[v]，
（4）源程式2，
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int f[20001]={0}; int v,n; scanf("%d%d",&v,&n); int w[31]; int i,j; for (i=1;i<=n;i++) { scanf("%d",&w[i]); } for (i=1;i<=n;i++) for (j=v;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+w[i]); } printf("%d\n",v-f[v]); return 0; }
將上面的源程式提交給洛谷題庫P1049 [NOIP2001 普及組] 裝箱問題（https://www.luogu.com.cn/problem/P1049），測評結果為“Accepted”，
【例4】數字組合
問題描述
有n個正整數，找出其中和為t（t也是正整數）的可能的組合方式，如：
n=5，5個數分別為1,2,3,4,5，t=5；
那么可能的組合有5=1+4和5=2+3和5=5三種組合方式，
輸入
輸入的第一行是兩個正整數n和t，用空格隔開，其中1<=n<=20，表示正整數的個數，t為要求的和（1<=t<=1000）
接下來的一行是n個正整數，用空格隔開，
輸出
和為t的不同的組合方式的數目，
輸入樣例
5 5
1 2 3 4 5
輸出樣例
3
（1）編程思路，
將輸入的和值t看成背包的總容量，輸入的每個正整數看成一件物品，其重量就是正整數本身，就是一個簡單的0/1背包問題，
設f[i]表示構成和值i的不同組合方式的數目，初始時，f[0]=1（背包中什么正整數沒放，肯定是0，和值0肯定有1種組合方式），其余元素全部為0，
顯然，對于正整數a，如果加入背包，則有f[j]=f[j]+f[j-a]，
（2）源程式，
#include <stdio.h> #include <string.h> int main() { int n,t; scanf("%d%d",&n,&t); int i,j; int f[1005]={0}; f[0]=1; for (i=1;i<=n;++i) { int a; scanf("%d",&a); for (j=t;j>=a;j--) f[j]+=f[j-a]; } printf("%d\n",f[t]); return 0; }
【例5】積木城堡
題目描述
XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡，城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木，小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒，所以他在壘城堡的時候總是遵循這樣的規則，
小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度，為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執，可是他發現自己在壘城堡的時候并沒有預先考慮到這一點，所以他現在要改造城堡，由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案，他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高，為了使他的城堡更雄偉，他覺得應該使最后的城堡都盡可能的高，
任務：
請你幫助小XC編一個程式，根據他壘的所有城堡的資訊，決定應該移去哪些積木才能獲得最佳的效果，
輸入
第一行是一個整數N（N<=100），表示一共有N座城堡，以下N行每行是一系列非負整數，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長，用-1結束，一座城堡中的積木不超過100塊，每塊積木的棱長不超過100，
輸出
一個整數，表示最后城堡的最大可能的高度，如果找不到合適的方案，則輸出0，
輸入樣例
2
2 1 –1
3 2 1 -1
輸出樣例
3
（1）編程思路，
塔好積木再拿走就相當于當初搭的時候沒選拿走的積木，這樣一轉化，問題就清楚了，把積木可搭建的最大高度看成背包的載重，每塊積木的高度就是物品的重量，也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下盡量多，
這樣就變成典型的0/1背包問題了，對于每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可，
定義二維陣列int f[101][10001]，其中元素f[i][j]=1表示第i座城堡高度為j可搭出，f[i][j]=0表示第i座城堡高度為j不能搭出，
狀態轉移方程為： f[i][j]=f[i][j-a[k]] { f[i][j-a[k]]=true} 其中a[k]表示第i座城堡所用的第k塊積木的棱長，
初始時，f[i][0]=1，每座城堡高度為0肯定可以搭出來，
從所有城堡高度的最小值開始列舉，若對于某一高度值h，所有的f[1][h]~f[n][h]均為1，則h就是最后城堡的最大可能的高度，
（2）源程式，
#include <stdio.h> int f[101][10001]={0}; int main(void) { int n; scanf("%d",&n); int i,j,k; int a[101]; int min=10001; for (i=1;i<=n;i++) { int cnt=1; int sum=0; int x; while (1) { scanf("%d",&x); if (x==-1) break; sum+=x; a[cnt++]=x; } if (min>sum) min=sum; f[i][0]=1; for (j=1;j<cnt;j++) for (k=sum;k>=a[j];k--) { if (f[i][k-a[j]]==1) f[i][k]=1; } } for (i=min;i>0;i--) { for (j=1;j<=n;j++) if (f[j][i]==0) break; if (j>n) break; } printf("%d\n",i); return 0; }
將上面的源程式提交給洛谷題庫P1504 積木城堡（https://www.luogu.com.cn/problem/P1504），測評結果為“Accepted”，
【例6】湊零錢
問題描述
韓梅梅喜歡滿宇宙到處逛街，現在她逛到了一家火星店里，發現這家店有個特別的規矩：你可以用任何星球的硬幣付錢，但是絕不找零，當然也不能欠債，韓梅梅手邊有 10000枚來自各個星球的硬幣，需要請你幫她盤算一下，是否可能精確湊出要付的款額，
輸入
輸入第一行給出兩個正整數：N（≤10000）是硬幣的總個數，M（≤100）是韓梅梅要付的款額，第二行給出 N 枚硬幣的正整數面值，數字間以空格分隔，
輸出
在一行中輸出硬幣的面值 V1≤V2≤?≤Vk，滿足條件 V1 +V2 +...+Vk =M，數字間以 1 個空格分隔，行首尾不得有多余空格，若解不唯一，則輸出最小序列，若無解，則輸出 No Solution，
注：我們說序列{ A[1],A[2],? }比{ B[1],B[2],? }“小”，是指存在 k≥1 使得 A[i]=B[i] 對所有 i<k 成立，并且 A[k]<B[k]，
輸入樣例
8 9
5 9 8 7 2 3 4 1
輸出樣例
1 3 5
（1）編程思路，
將要付的款額M看成背包的總容量，將N枚物品的面值看成裝入背包中物品的重量，本題實際上就是看用這N枚硬幣能否裝滿容量為M的背包，若能裝滿，輸出字典序最小的裝載方案，
定義陣列int f[105]；其中f[i]表示容量為i的背包是否能裝滿，初始時f[0]=1（肯定存在背包中什么不裝的方案），其余f[i]全為0，
顯然，若 f[j-a[i]]=1，容量為j-a[i]的背包可以裝滿，則加入面值為a[i]的硬幣后，容量為j的背包也可裝滿，即f[j]=1，
為了記錄路徑，定義陣列int path[10005][105];，該陣列記錄當前狀態是由哪個狀態轉移過來的，初始值也全為0，
若f[j-a[i]]=1，則一定可得到f[j]=1，則記錄f[i][j]=1，表示容量為j的背包是加入了面值為a[i]的硬幣，
因為裝入的方案可能有多種，為了輸出字典序最小的方案，顯然應該用面值盡可能小的硬幣來裝，為此，將保存面值的陣列a先按從大到小的順序排序，這樣進行0/1背包時，物品的加入是按面值大的先加入背包，面值小的后加入背包，這樣后面加入的更小的面值方案會覆寫前面加入的面值較大的方案，從而實作輸出字典序最小的硬幣方案，
（2）源程式，
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int cmp(int a,int b) { return a>b; } int path[10005][105]; int main() { int n,m; scanf("%d %d",&n,&m); int f[105],a[10005]; int i,j; for (i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,0,sizeof(f)); memset(path,0,sizeof(path)); f[0]=1; sort(a+1,a+n+1,cmp); for (i=1;i<=n;i++) { for (j=m;j>=a[i];j--) { if (f[j-a[i]]==1) { f[j]=1; path[i][j]=1; } } } if (f[m]>0) { i=n , j = m; int flag = 0; while (i>0 && j>=0) { if (path[i][j]) // 當前狀態可選 { if (flag==0) { printf("%d",a[i]); flag = 1;} else printf(" %d",a[i]); j -= a[i]; } i--; } printf("\n"); } else printf("No Solution\n"); return 0; }
【例7】烹調方案
題目描述
gw希望能在T時間內做出最美味的食物，可使用的食材一共有n件，每件食材有三個屬性，ai，bi和ci，如果在t時刻完成第i樣食材則得到ai-t*bi的美味指數，用第i件食材做飯要花去ci的時間，
眾所周知，gw的廚藝不怎么樣，所以他需要你設計烹調方案使得美味指數最大，
輸入
第一行是兩個正整數T和n（1<=n<=50），表示控制時間和食材個數，
下面一行n個整數，ai
下面一行n個整數，bi
下面一行n個整數，ci，所有數字均小于100,000
輸出
輸出最大美味指數
輸入樣例
74 1
502
2
47
輸出樣例
408
（1）編程思路，
一般的背包問題中，每個物品的重量和價值是固定的，因此物品的裝入順序對結果不產生影響，
在本題中，因為每種食材的加工完成時刻t不同，其得到的美味指數不一樣，美味指數與時刻t存在線性的關系，因此，需要考慮每種食材的加工順序，
考慮相鄰的兩個食材x,y，假設現在已經耗費p的時間，若先加工食材x，再加工y，得到的美味指數為：
a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*b[y] （式①）
若先加工食材x，再加工y，得到的美味指數為：
a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*b[x] （式②）
對這兩個式子化簡，得到①＞②的條件是 c[x]*b[y]<c[y]*b[x]，
只要滿足上面這個條件，則對于食材對(x,y)，x在y之前進行加工得到的美味指數一定最大，
定義結構體陣列
struct node
{
long long a, b, c;
} m[51];
來保存輸入的各食材資料，
將結構體陣列按成員分量c/b從小到大的順序排列后，按陣列中的順序依次加工食材（也就是依次加入背包），就是簡單的0/1背包問題了，
（2）源程式，
#include <stdio.h> long long max(long long a,long long b) { return a>b?a:b; } struct node { long long a, b, c; }; int main() { int t,n; scanf("%d%d",&t,&n); struct node m[51]; int i,j; for (i = 1; i <= n; i++) scanf("%lld",&m[i].a); for (i = 1; i <= n; i++) scanf("%lld",&m[i].b); for (i = 1; i <= n; i++) scanf("%lld",&m[i].c); for (i=1;i<n;i++) for (j=1;j<=n-i;j++) if (m[j].c*m[j+1].b>m[j+1].c*m[j].b) { struct node temp; temp=m[j]; m[j]=m[j+1]; m[j+1]=temp; } long long f[100001]={0}; long long ans=0; for (i = 1; i <= n; i++) for (j = t; j>= m[i].c; j--) { f[j] = max(f[j], f[j-m[i].c] + m[i].a - j*m[i].b); ans = max(f[j], ans); } printf("%lld\n",ans); return 0; }
將上面的源程式提交給洛谷題庫P1417 烹調方案（https://www.luogu.com.cn/problem/P1417），測評結果為“Accepted”，
【例8】多米諾骨牌
問題描述
多米諾骨牌由上下2個方塊組成，每個方塊中有1～6個點，現有排成行的上方塊中點數之和記為S1，下方塊中點數之和記為S2，它們的差為|S1-S2 |，
如圖，S1=6+1+1+1=9，S2=1+5+3+2=11， |S1-S2|=2，
每個多米諾骨牌可以旋轉180°，使得上下兩個方塊互換位置，請你計算最少旋轉多少次才能使多米諾骨牌上下2行點數之差達到最小，
對于圖中的例子，只要將最后一個多米諾骨牌旋轉180°，即可使上下2行點數之差為0，
輸入
輸入檔案的第一行是一個正整數 n (1≤n≤1000)，表示多米諾骨牌數，接下來的n行表示n 個多米諾骨牌的點數，每行有兩個用空格隔開的正整數，表示多米諾骨牌上下方塊中的點數 a和b，且1≤a,b≤6，
輸出
輸出檔案僅一行，包含一個整數，表示求得的最小旋轉次數，
輸入樣例
4
6 1
1 5
1 3
1 2
輸出樣例
1
（1）編程思路，
不管骨牌這樣旋轉變換，其上下兩行數字和s1+s2=sum，得到的總和sum是不會變的，
題目要求的是上下兩行數字和最小差值情況下的最小交換次數，直接表示差值，可能有正有負，不太方便，我們可以轉化一下，保存某一行的數字和（例如上面的第1行的數字和S1），由于每次旋轉交換只是把上下兩個數交換，所有骨牌上下兩行數的總和sum是不變的，這樣差值就容易求出來了，|sum-s1-s1|就是所求上下兩行數字和的差值了，
設 f[i][j] 表示前i個數字，第一行的數字和是j時，最小的交換次數，初始值所有f[i][j]都是無窮大（本題中可以直接設定為300000，就足夠大了），f[1][a[1]]=0（第1張骨牌第1行的和值為自身，顯然不用交換），f[1][b[1]]=1（第1張骨牌第1行的和值為下面的數字，需要旋轉180°，交換1次），（陣列a[]和b[]分別保存第一行和第二行各骨牌上面的數字）
由于n張骨牌的點數和最大可能為6*n，因此可以將背包容量看成6*n，之后從第2張骨牌開始，每張骨牌加入背包中，考慮狀態轉移
if (j-a[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-a[i]]); // 當前不交換
if (j-b[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-b[i]]+1); // 當前交換
最后再列舉一下前n個骨牌第一行的和f[n][i]，找出使絕對值abs(sum-i-i)最小的f[n][i]就是所求的最小交換次數，
（2）源程式，
#include <stdio.h> int min(int a,int b) { return a<b?a:b; } int abs(int a) { return a>0?a:-a; } int a[1005],b[1005],f[1005][6005]; int main() { int n; scanf("%d",&n); int i,j; int sum=0; for (i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); sum+=a[i]+b[i]; } for (i=1;i<=n;i++) for (j=0;j<=6*n;j++) f[i][j]=300000; f[1][b[1]]=1; f[1][a[1]]=0; for (i=2;i<=n;i++) { for (j=0;j<=6*n;j++) { if(j-a[i]>=0) f[i][j]=min(f[i][j],f[i-1][j-a[i]]); if(j-b[i]>=0) f[i][j]=min(f[i][j],f[i-1][j-b[i]]+1); } } int ans=300000,diff=300000; for (i=0;i<=sum;i++) { if (f[n][i]!=300000) { if (abs(sum-i-i)<diff) { diff=abs(sum-i-i); ans=f[n][i]; } else if (abs(sum-i-i)==diff) ans=min(ans,f[n][i]); } } printf("%d\n",ans); }
將上面的源程式提交給洛谷題庫P1282 多米諾骨牌（https://www.luogu.com.cn/problem/P1282），測評結果為“Accepted”，
【例9】豪華游輪
問題描述
有一條豪華游輪（其實就是條小木船），這種船可以執行4種指令：
right X : 其中X是一個1到719的整數，這個命令使得船順時針轉動X度，
left X : 其中X是一個1到719的整數，這個命令使得船逆時針轉動X度，
forward X : 其中X是一個整數（1到1000），使得船向正前方前進X的距離，
backward X : 其中X是一個整數（1到1000），使得船向正后方前進X的距離，
隨意的寫出了n個命令，找出一個種排列命令的方法，使得船最終到達的位置距離起點盡可能的遠，
輸入
第一行一個整數n(1 <= n <= 50)，表示給出的命令數，
接下來n行，每行表示一個命令，
輸出
一個浮點數，能夠走的最遠的距離，四舍五入到6位小數，
輸入樣例
3
forward 100
backward 100
left 90
輸出樣例
141.421356
（1）編程思路，
這種船可以執行的4種指令可以分成3種情況：向前走、向后走、旋轉一定的角度（或者順時針、或者逆時針），
為了能夠走最遠的距離，顯然應該把所有向前走的指令全部合并起來，一直向前走得到一條邊sumf，把所有向后走的指令也全部合并起來，一直向后走也得到另一條邊sumb，再將所有的旋轉指令有機組合起來，通過它們的旋轉組合，形成兩條邊sumf與sumb的夾角，這個夾角越接近180度，夾角所對應的第3條邊（也是船走的距離）就越大，
因此本題實際是一個變形的0/1背包問題，
設f[i][j]表示執行前i條旋轉指令后，夾角為j是否可得到，初始值除f[0][0]=1外，其余全部為0，
之后按0/1背包的處理方法，將各旋轉指令作為一個個的物品加入容量為360的背包中，指令中的旋轉角度ang[i]看成是物品的重量，則有狀態轉移方式為：
若f[i-1][j]=1，則f[i][j]=1 （第i條指令不加入背包中）
f[i][(j+ang[i]+720)%360]=1 （第i條指令加入背包中）
按照0/1背包處理完后，然后遍歷f[cnt][i] （cnt為旋轉指令的條數）求得離180最近的角度，再用余弦公式計算出第3條邊就可以了，
在這里我們只需要通過讓加入背包的旋轉指令使得旋轉的度數盡量接近180°就可以了，而沒有加入背包的旋轉指令只需要在走完后，再執行沒有加入背包的旋轉指令，在原地旋轉一通，并不影響走的總距離，
（2）源程式，
#include <stdio.h> #include <math.h> # define PI 3.1415926535 int min(int a,int b) { return a<b?a:b; } int abs(int a) { return a>0?a:-a; } int main() { int n; scanf("%d",&n); int i,j; int sumf=0,sumb=0; // 向前走的總距離和向后走的總距離 int ang[55]; int cnt=0; for (i=1;i<=n;i++) { int x; char ch[11]; scanf("%s%d",ch,&x); if (ch[0]=='f') sumf+=x; if (ch[0]=='b') sumb+=x; if (ch[0]=='r') ang[++cnt]=x; if (ch[0]=='l') ang[++cnt]=-x; } int f[105][405]={0}; f[0][0]=1; for (i=1;i<=cnt;i++) for (j=0;j<360;j++) if (f[i-1][j]) { f[i][j]=1; f[i][(j+ang[i]+720)%360]=1; } int p=180; for (i=0;i<360;i++) if (f[cnt][i]) p=min(p,abs(i-180)); double ans=sqrt(sumf*sumf+sumb*sumb+2*sumb*sumf*cos(p*PI/180)); printf("%.6f\n",ans); return 0; }
將上面的源程式提交給洛谷題庫P2625 豪華游輪（https://www.luogu.com.cn/problem/P2625），測評結果為“Accepted”，
【例10】奶牛博覽會
問題描述
奶牛想證明它們是聰明而風趣的，為此，貝西籌備了一個奶牛博覽會，她已經對N頭奶牛進行了面試，確定了每頭奶牛的智商和情商，
貝西有權選擇讓哪些奶牛參加展覽，由于負的智商或情商會造成負面效果，所以貝西不希望出展奶牛的智商之和小于零，或情商之和小于零，滿足這兩個條件下，她希望出展奶牛的智商與情商之和越大越好，請幫助貝西求出這個最大值，
輸入
第一行：單個整數N，1≤N≤100，
第二行到第 N+1行：第 i+1行有兩個整數：Si和Fi，表示第i頭奶牛的智商和情商，? 1000≤Si，Fi ≤1000，
輸出
輸出單個整數：表示情商與智商和的最大值，貝西可以不讓任何奶牛參加展覽，如果這樣做是最好的，輸出0，
輸入樣例
5
-5 7
8 -6
6 -3
2 1
-8 -5
輸出樣例
8
（1）編程思路，
本題可以用0/1背包模型求解，把智商當成“物品體積”，情商當成“物品價值”來解決問題，
但由于題目中，智商和情商均可以為負數，因此需要對負數進行處理，
由題目可知，最多100頭牛，每頭牛的智商在-1000~1000之間，即智商和（背包容量）在-100000至100000之間，由于陣列下標不能為負數，考慮將原點0右移100000，即用下標0~200000來對應這些智商和，下標范圍0~99999來對應負數，下標100000對應為0，下標范圍100000~200000來對應正數，
套用0/1背包模型時要注意，對于正數逆序求解（這是0/1背包模型的基本套路），例如
for (j=200000;j>=s[i];j--)
f[j]=max(f[j],f[j-s[i]]+f[i]);
但對于負數，由于j-s[i]>j，因此不能逆向推，采用正向求解，例如
for(int j=0;j<=200000+s[i];j++)
f[j]=max(f[j],f[j-s[i]]+f[i]);
最后，找到下標范圍為100000~200000（對應智商不為負數）內，i+f[i]-100000（f[i]>0）的最大值就是問題的答案，
（2）源程式，
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int f[200005]; int main() { int n; scanf("%d",&n); int s[105],f[105]; int i,j; for (i=1;i<=n;i++) scanf("%d%d",&s[i],&f[i]); memset(f,-0x3f,sizeof(f)); f[100000]=0; for (i=1;i<=n;i++) { if(s[i]>0) for (j=200000;j>=s[i];j--) f[j]=max(f[j],f[j-s[i]]+f[i]); else for(int j=0;j<=200000+s[i];j++) f[j]=max(f[j],f[j-s[i]]+f[i]); } int ans=0; for (i=100000;i<=200000;i++) if(f[i]>=0) ans=max(ans,i+f[i]-100000); printf("%d\n",ans); return 0; }
將上面的源程式提交給北大OJ題庫POJ 2184 Cow Exhibition（http://poj.org/problem?id=2184），可以Accepted，
練習題
1．P1164 小A點菜（https://www.luogu.com.cn/problem/P1164）
#include <stdio.h> #include <string.h> int main() { int n,m; scanf("%d%d",&n,&m); int i,j; int f[10001]={0}; f[0]=1; for (i=1;i<=n;++i) { int a; scanf("%d",&a); for (j=m;j>=a;j--) f[j]+=f[j-a]; } printf("%d\n",f[m]); return 0; }View Code
2．P1877 [HAOI2012]音量調節（https://www.luogu.com.cn/problem/P1877）
#include <stdio.h> int main(void) { int c[1001]; int f[51][1001]={0}; // f[i][j]=1表示第i首歌是否能為音量j int n,begin,max; scanf("%d%d%d",&n,&begin,&max); f[0][begin]=1; int i,j; for (i=1;i<=n;i++) scanf("%d",&c[i]); for (i=1;i<=n;i++) { for (j=0;j<=max;j++) { if (f[i-1][j]) { if(j+c[i]<=max) f[i][j+c[i]]=1; if(j-c[i]>=0) f[i][j-c[i]]=1; } } } for (i=max;i>=0;i--) { if (f[n][i]==1) { printf("%d\n",i); return 0; } } printf("-1\n"); return 0; }View Code
3．P1926 小書童——刷題大軍（https://www.luogu.com.cn/problem/P1926）
#include <stdio.h> int main() { int n,m,k,r; scanf("%d%d%d%d",&n,&m,&k,&r); int t1[11],t2[11],s[11]; int i,j; for (i=1;i<=n;i++) scanf("%d",&t1[i]); for (i=1;i<=m;i++) scanf("%d",&t2[i]); for (i=1;i<=m;i++) scanf("%d",&s[i]); int f[151]={0}; f[r]=0; for (i=1;i<=m;i++) { for (j=r;j>=t2[i];j--) { if (f[j]<f[j-t2[i]]+s[i]) f[j]=f[j-t2[i]]+s[i]; } } for (i=0;i<=r;i++) if (f[i]>=k) break; int res=r-i; int cnt=0; for (i=1;i<n;i++) for (j=1;j<=n-i;j++) if (t1[j]>t1[j+1]) { int t=t1[j]; t1[j]=t1[j+1]; t1[j+1]=t; } for (i=1;i<=n;i++) { if (t1[i]<=res) { cnt++; res-=t1[i]; } else break; } printf("%d\n",cnt); return 0; }View Code
4．P2370 yyy2015c01 的U盤（https://www.luogu.com.cn/problem/P2370）
#include <stdio.h> int max(int a,int b) { return a>b?a:b; } struct Node { int w,v; }; struct Node a[1005]; int main() { int n,p,s; scanf("%d%d%d",&n,&p,&s); int i,j; for (i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].v); int f[1005]={0}; for (i=1;i<n;i++) for (j=1;j<=n-i;j++) if (a[j].w>a[j+1].w) { struct Node temp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } for (i=1;i<=n;i++) { for (j=s;j>=a[i].w;j--) { f[j]=max(f[j],f[j-a[i].w]+a[i].v); if (f[j]>=p) { printf("%d\n",a[i].w); return 0; } } } printf("No Solution!\n"); return 0; }View Code
5．P2392 kkksc03考前臨時抱佛腳（https://www.luogu.com.cn/problem/P2392）
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int s[5]; int i,j,k; for (i=1;i<=4;i++) scanf("%d",&s[i]); int opt[1201],time[21]; int ans=0; for (i=1;i<=4;i++) { int sum=0; for (j=1;j<=s[i];j++) { scanf("%d",&time[j]); sum+=time[j]; } memset(opt,0,sizeof(opt)); for (j=1;j<=s[i];j++) for (k=sum/2;k>=time[j];k--) opt[k]=max(opt[k],opt[k-time[j]]+time[j]); ans+=sum-opt[sum/2]; } printf("%d\n",ans); return 0; }View Code
6．POJ 1745 Divisibility（http://poj.org/problem?id=1745）
// 設 f[i][j]表示前i個數通過一系列加減運算后余數能否為j， // 初始化f為0, 然后f[1][a[1]%k] = 1 // if(f[i - 1][j]) // f[i][(j + a[i])%k] = 1; // f[i][(j - a[i])%k] = 1; （i=2~n，j=0~k-1） #include <stdio.h> #define maxn 10005 int f[maxn][105]={0}; int main() { int n,k,i,j,a[maxn]; scanf("%d%d",&n,&k); for (i=1; i<=n;i++) { scanf("%d",&a[i]); a[i]%=k; } f[1][((a[1] % k) + k) % k] = 1; for (i = 2; i <= n; i++) { for (j = 0; j<k; j++) { if (f[i-1][j]) { f[i][((j + a[i]) % k + k) % k] = 1; f[i][((j - a[i]) % k + k) % k] = 1; } } } if (f[n][0]) printf("Divisible\n"); else printf("Not divisible\n"); return 0; }View Code
7．POJ 1837 Balance（http://poj.org/problem?id=1837）
// 一個天平左右臂各長為15，給出天平上C個掛鉤的位置，再給出G個砝碼的重量， // 問有多少種方法能使這個天平保持平衡， // 設f[i][j]表示把前i個物品全部掛上時使天平達到平衡度為j的方案數， // 則狀態轉移方程為： f[i][j+w[i]*c[k]]+=f[i-1][j] ; // 將g個掛鉤掛上的極限值：15*25*20==7500 // 那么在有負數的情況下是-7500~~7500,以0為平衡點 // 可以將平衡點往右移7500個單位，范圍就是0~~15000 ，這樣就好處理多了 #include <stdio.h> #include <string.h> int f[21][15005]; int main() { int c,g,i,j,k,w[25],a[25]; scanf("%d%d",&c,&g); for (i=1;i<=c;i++) scanf("%d",&w[i]); for (i=1;i<=g;i++) scanf("%d",&a[i]); memset(f,0,sizeof(f)); f[0][7500]=1; for (i=1;i<=g;i++) for (j=0;j<=15000;j++) { if (f[i-1][j]!=0) for (k=1;k<=c;k++) f[i][j+a[i]*w[k]]+=f[i-1][j]; } printf("%d\n",f[g][7500]); return 0; }View Code
8．POJ 3459 Projects（http://poj.org/problem?id=3459）
#include <stdio.h> #include <string.h> int max(int a,int b) { return a>b?a:b; } int main() { int f[110][110]; // f[i][j]表示前i個工程，分配j個人完成的最大期望利潤 int p[110][110]; int cost[110][110]; int t; scanf("%d",&t); while (t--) { int m,n,c; scanf("%d%d%d",&m,&n,&c); int i,j,k; for (i=1;i<=m;i++) for (j=1;j<=n+2;j++) scanf("%d",&p[i][j]); for (i=1;i<=m;i++) for (j=0;j<=n;j++) cost[i][j]=p[i][j]*(p[i][n+1]-c*j)-(100-p[i][j])*p[i][n+2]; for (i=1;i<=n;i++) f[0][i]=-100*c*i; for (i=1;i<=m;i++) f[i][0]=-1*p[i][n+2]*100+f[i-1][0]; for (i=1;i<=m;i++) for (j=1;j<=n;j++) { f[i][j]=-0x7f7f7f7f; for (k=0;k<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k]+cost[i][k]); } int ans=-0x7f7f7f7f; for (i=0;i<=n;i++) if (ans<f[m][i]) ans=f[m][i]; printf("%d\n",ans); for (i=0;i<=n;i++) if (f[m][i]==ans) printf("%d ",i); printf("\n"); } return 0; }View Code
9．POJ 3624 Charm Bracelet（http://poj.org/problem?id=3624）
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int main() { int opt[12885]={0}; int w[3405],d[3405]; int n,m; scanf("%d%d",&n,&m); int i,j; for (i=1;i<=n;i++) { scanf("%d%d",&w[i],&d[i]); } for (i=1;i<=n;i++) for (j=m;j>=w[i];j--) { opt[j]=max(opt[j],opt[j-w[i]]+d[i]); } printf("%d\n",opt[m]); return 0; }View Code
10．POJ 3628 Bookshelf 2（http://poj.org/problem?id=3628）
#include <stdio.h> int max(int a,int b) { if (a>b) return a; else return b; } int f[20000005]={0}; int main() { int h[25]; int n,b; scanf("%d%d",&n,&b); int i,j; int sum=0; for (i=1;i<=n;i++) { scanf("%d",&h[i]); sum+=h[i]; } for (i=1;i<=n;i++) for (j=sum;j>=h[i];j--) { f[j]=max(f[j],f[j-h[i]]+h[i]); } int ans; for (i=1;i<=sum;i++) if (f[i]>=b) { ans=f[i]-b; break; } printf("%d\n",ans); return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452807.html
標籤：C