DP 一直是心中痛，不多說了，這個暑假就坑在這上了。

這暑假第一道DP題，01背包問題。

題意是說物品有 重量和價值 ，但你能承受的重量有限，問你能帶的最大價值。

這題數組開大點，盡管不知道有啥坑點，可是我數組開得大，直接1A了。

想想自己DP都是大問題，還要給學弟講（tiao）題（jiao），真是憂傷。

僅僅能這幾天通宵點出 DP 天賦。順便貼上自己的理解，反正我也準備這樣給學弟講，假設有誤，請路過大神指正。

論01背包的自我修養：


?? ??? ?N個物品，M容量的包，最大價值為W。
?? ??? ?
?? ??? ?第 i 件物品分別有 Vi 的重量和 Ci 的價值。
?? ??? ?

?? ??? ??? ?N = 4 ，M= 6 。

?? ??? ??? ?V?? ??? ?C
?? ??? ??? ?
?? ??? ?1：?? ?1?? ??? ?4
?? ??? ?2：?? ?2?? ??? ?6
?? ??? ?3：?? ?3?? ??? ?12
?? ??? ?4：?? ?2?? ??? ?7
?? ??? ?
?? ??? ?int dp[10001],c[10001],v[10001];
?? ??? ?
?? ??? ?//分別為背包的價值，物品的價值，物品重量。
?? ??? ?
?? ??? ?memset(dp,0,sizeof(dp));
?? ??? ?

?? ??? ?//初始化背包?? ?畢竟沒放東西的時候是沒有價值的

?????? //還有其它初始化為-INF 的情況，僅僅有dp[0]=0。這是要求：恰好裝滿的最大價值。

?? ??? ?
?? ??? ?for ( int i = 0 ;? i < n? ; i++)
?? ??? ?{
?? ??? ??? ?//從第一件物品開始放
?? ??? ??? ?
?? ??? ??? ?for ( int j = m ; j-v [i] >= 0 ; j--)?? ?// j - v[i] >=0防止數組越界，畢竟背包容量不能為負
?? ??? ??? ?{
?? ??? ??? ??? ?//背包每次減去1，看能不能放進去這件物品
?? ??? ??? ??? ?
?? ??? ??? ??? ?//printf("%d:max(%d,%d) ",j,dp[j],dp[j-c[i]]+v[i]);
?? ??? ??? ??? ?
?? ??? ??? ??? ?dp[j] = max ( dp[j] , dp[ j-v[i] ] + c[i] );
?? ??? ??? ?
?? ??? ??? ??? ?//當背包容量為j的時候，能放進去添加價值，就放進去
?? ??? ??? ??? ?
?? ??? ??? ??? ?//dp[j] 容量為j的時候的價值
?? ??? ??? ??? ?
?? ??? ??? ??? ?//dp[ j-c[i] ] + c [i]? （容量j減去當前物品的重量=剩余容量） 的價值 + 當前物品的價值
?? ??? ??? ??? ?
?? ??? ??? ??? ?//價值當然越大越好 取max
?? ??? ??? ??? ?
?? ??? ??? ??? ?//當 j - v[i] < 0表明背包已經不能放了。
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ?}
?? ??? ?
?? ??? ?容量：max（前一個價值，放入當前物品后的價值）
?? ??? ?
?? ??? ?6 :max(0,4) ?? ??? ?5 :max(0,4) ?? ??? ?4 :max(0,4)?? ?? ?? 3 :max(0,4) ?? ??? ?2 :max(0,4) ?? ??? ?1 :max(0,4)
?? ??? ?6 :max(4,10) ?? ?? 5 :max(4,10) ?? ?? 4 :max(4,10) ?? ?? 3 :max(4,10) ? ? ? 2 :max(4,6)
?? ??? ?6 :max(10,22) ?? ?5 :max(10,18) ?? ?4 :max(10,16) ?? ?3 :max(10,12)
?? ??? ?6 :max(22,23) ?? ?5 :max(18,19) ?? ?4 :max(16,13) ?? ?3 :max(12,11) ?? ?2 :max(6,7)
?? ??? ?
?? ??? ?
?? ??? ?最后背包 從容量 0 ~ 6 所能有的價值，取其最大值。
?? ??? ?

?? ??? ?M：W?? ?? 0?? ??? ?1?? ??? ?2??????? 3?? ? ? ?? 4 ? ?? ?? 5 ? ? ???? 6

?? ??? ??? ??? ????????? 0:0 ?? ?1:4 ?? ?2:7 ?? ?3:12 ?? ?4:16 ?? ?5:19 ?? ?6:23
?? ??? ??? ??? ?
?? ??? ?
?? ??? ?這時候背包裝滿的情況 價值W最大，為23。
?? ????

#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int dp[1000001]; int c[100001],v[100001]; int n,m;int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)scanf("%d%d",&c[i],&v[i]);memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){for(int j=m;j-c[i]>=0;j--){dp[j]=max(dp[j],dp[j-c[i]]+v[i]);}}int ans=0;for(int i=0;i<=m;i++)ans=max(ans,dp[i]);printf("%d\n",ans);} }

總結

以上是生活随笔為你收集整理的POJ 3624 Charm Bracelet的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。