1. 貨幣系統
1371. 貨幣系統 - AcWing題庫
給定?V?種貨幣（單位：元），每種貨幣使用的次數不限。
不同種類的貨幣，面值可能是相同的。
現在，要你用這?V?種貨幣湊出?N?元錢，請問共有多少種不同的湊法。
解題思路
我們兩層循環分別枚舉到第i種物品了，價值為j
如果枚舉的價值大于當前枚舉物品的價值就將f[i][j]的值賦為f[i][j-w[i]].這個值記錄用w[i]湊到j的方法數量
不選的方法與f[i-1][j]的值相同。即不用w[i]湊到j的方法
AC代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>using namespace std;int v,n;
long long w[30];
long long f[30][10010];//前i種物品選擇價值為j的方案數
int main()
{scanf("%d%d",&v,&n);for(int i=1;i<=v;i++){scanf("%d",&w[i]);}f[0][0]=1;for(int i=1;i<=v;i++){for(int j=0;j<=n;j++){if(j>=w[i])//選了{f[i][j]=f[i][j-w[i]];//湊f[i][j-w[i]](即少選一次w[i]的方法) 有幾個方法，就是用w[i] 來湊到j的方法}//沒選f[i][j]+=f[i-1][j];//加上沒有這個i的方法,即不用w[i]來湊到j的方法}}printf("%lld",f[v][n]);return 0;
}2. 01背包
2. 01背包問題 - AcWing題庫
有?N件物品和一個容量是?V?的背包。每件物品只能使用一次。
第?i?件物品的體積是?vi，價值是?wi。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。
?解題思路
兩層循環分別來枚舉，到第i個物品，體積不小于j
如果j小于v[i]（v這個數組用來記錄i個物品的體積，w數組用來記錄價值）那只能不拿，價值就是不選i體積為j的價值
如果不小于就可以選擇拿還是不拿，將拿了第i個物品體積才到j與不拿這個物品體積就到j的價值進行比較取較大值
AC代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N, V;
int v[1010];
int w[1010];
int f[1010][1010];//前i件物品中，尋找不超過j個體積的最大價值
int main()
{scanf("%d%d", &N, &V);for (int i = 1; i <= N; i++){scanf("%d%d", &v[i], &w[i]);}for(int i=1;i<=N;i++)//前{for(int j=0;j<=V;j++)//體積{if(j<v[i])//不能拿{f[i][j]=f[i-1][j];//與沒i是一樣的，取值為不選第i件物品體積為j的最大價值}else//可以拿{f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i-1][j]);//比較不拿第i件物品體積達到j與拿了第i件物品體積達到j誰更大}}}printf("%d\n", f[N][V]);return 0;
}?3. 完全背包
有?N?種物品和一個容量是?V?的背包，每種物品都有無限件可用。
第?i 種物品的體積是?vi，價值是?wi。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。
解題思路
與01背包不同的是完全背包的每一種都可以無限選擇，所以它選擇第i個不用使i-1后再統計j-v[i]，因為之前可能使用過i了沒使用(或使用了不如不用)那f[i][j-v[i]]也在之前初始化為了f[i-1][j-v[i]]
AC代碼
#include<iostream>
#include<cstring>
#include<cstdio>using namespace std;int N,V;
int v[1010];
int w[1010];int f[1010][1010];int main()
{scanf("%d%d",&N,&V);for(int i=1;i<=N;i++){scanf("%d %d",&v[i],&w[i]);}for(int i=1;i<=N;i++)//枚舉第i件物品{for(int j=0;j<=V;j++){if(j<v[i])//不能放{f[i][j]=f[i-1][j];//統計沒放的}else//能放f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);//沒放這一次的價值，即選了k-1次i物品的價值}}cout<<f[N][V]<<endl;return 0;
}4. 砝碼稱重
你有一架天平和?N?個砝碼，這?N?個砝碼重量依次是?W1,W2,???,WNW1,W2,···,WN。
請你計算一共可以稱出多少種不同的正整數重量？
注意砝碼可以放在天平兩邊。
?解題思路
兩層循環，枚舉第i個砝碼，能否湊成j的重量，存儲值為布爾類型
一個砝碼有三種情況，放在天平右邊(看當前重量減去這個砝碼重量是否能湊成(取絕對值，因為這邊超過另一半，超過的重量也成立))，放在左邊(同上不過是加上)與不放(看上一個可不可以即可)，只要有一種可以就能湊成。
將0個砝碼，0重量初始化為true，但最后累計時不能算上，因為只統計正整數，0不是
?AC代碼
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>using namespace std;int N;
int v[110];bool f[110][200010];int main()
{scanf("%d",&N);int sum=0;for(int i=1;i<=N;i++){scanf("%d",&v[i]);sum+=v[i];}f[0][0]=true;//0肯定能湊出來，什么也不放就行for(int i=1;i<=N;i++)//第i個{for(int j=0;j<=sum;j++)//湊j的重量，能否湊成{//1如果不放就能達到j這個重量那肯定可以，2如果放到左邊看不放之前有沒有這個重量f[i][j]=f[i-1][j]|f[i-1][j+v[i]]|f[i-1][abs(j-v[i])];//不放和放左邊和放右邊}}int res=0;for(int i=1;i<=sum;i++)//i不能從0開始因為0不是正整數{if(f[N][i])res++;}printf("%d",res);return 0;
}這篇就到這里啦（づ￣3￣）づ╭?? ～(?′?‵?)Ｉ L???????
