設f(i,x)表示前i件物品，背包容量為x時的最大價值，那么轉移式可以表示為f(i,x)=max(f(i-1,x-w[i]+c[i]),f(i-1,x)),那么f(n,m)即為最優解。其實整體思想則表示為從容量為1的開始計算并且后面的計算不斷的使用前面已經計算的值，這樣就可以避免重復計算。
還有一道貨幣系統問題，即已知貨幣系統有v種面值，求組成面值N的貨幣有多少種方案？ 【樣例輸入】 3（v) 10(N) 1 2 5(各種面值大小) 【輸出樣例】 10 題解： 主要思想就是另創一個數組，每讀入一種面值對其進行不斷加，最后看數組下標為N的大小即為ans。讓數組在循環體中滾動運算。 code
#include<iostream>#include<stdio.h>using namespace std;int f[1000];int main(void){ int v,n,p; cin>>v>>n; for(int i=1;i<=v;i++) { cin>>p; f[p]++; for(int j=p;j<=n;j++) //滾動計算 { f[j]+=f[j-p]; } } cout<<f[n]<<endl;}補上一次簡單背包中的一題 數字分組 Ural 1005 將一組數分成兩組，讓他們的和之差最小，求最小值。 【輸入樣例】 5 1 2 3 4 5 【輸出樣例】 1 題解： 其實這題轉換一下思路就可以化簡為之前用過的裝箱問題。即從n個物品中選若干個，求重量小于sum/2的最大值。 code
#include<iostream>#include<stdio.h>using namespace std;int f[1000],dp[1000];int main(void){ int n,sum=0,max; cin>>n; for(int i=1;i<=n;i++) { cin>>f[i]; sum+=f[i]; } max=sum/2; for(int i=1;i<=n;i++) { for(int j=max;j>=0;j--) //注意！這里要用倒序，不然會出現重復計算 { if(dp[j]) dp[j+f[i]]=1; } dp[f[i]]=1; } for(int i=max;i>=0;i--) { if(dp[i]) { cout<<sum-2*i<<endl; break; } }}最后是完全背包問題，其實如果0/1背包理解的話那這個就很好理解了 題目同0/1背包問題，唯一不同的地方是每種物品都有無限多個，求可以獲得的最大值 題解： 因為0/1背包有個數限制所以for循環是按照物品來的，而該題沒有這個限制故按照包的大小來計算 code:
#include<iostream>#include<stdio.h>using namespace std;int w[5000],c[5000],dp[5000]; int main(void){ int n,m,t; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>w[i]>>c[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(i>=w[j]) { t=dp[i-w[j]]+c[j]; if(t>dp[i]) dp[i]=t; } } } cout<<dp[m]<<endl;}新聞熱點
疑難解答
