題目鏈接:http://poj.org/problem?id=3624
?
poj1741。題意:一共給出n種手鐲,每個手鐲有著各自的重量以及魅力值,在m重量下能得到的最大魅力值是多少。
分析:標準的01背包。狀態轉移如此:
dp[i][j]表示前i個手鐲在重量為j的背包容量下能達到的最大魅力值。w[i]是第i個手鐲的重量,d[i]是第i個手鐲的魅力值。
如果某個超過背包重量,則一定不放入背包。問題則為剩余i-1個手鐲裝入重量的容量為j的背包得到的最大魅力值。
否則該手鐲放入背包。問題則為剩余i-1個手鐲裝入重量的容量為j-w[i]的背包能到的的最大價值加上手鐲i的價值d[i]。
if (w[i]>j) dp[i][j] = dp[i-1][j]
else dp[i][j] = max(dp[i-1][j-w[i]]+d[i],dp[i-1][j])
第一次用二維寫的,,,好吧,貌似只能用一維這題
手工模擬一下發現dp[i,j]只跟之前的某幾個值有關,再之前計算的結果就都沒用了...
所以我們就可以用一個數組來重復使用了,不過要倒序,保證無后效性...
?
Sample Input4 6 1 4 2 6 3 12 2 7 Sample Output23
?
AC代碼:
?
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<ctype.h> 5 #include<stdlib.h> 6 #include <iostream> 7 #include<algorithm> 8 #include<queue> 9 10 using namespace std; 11 12 #define N 13000 13 ///12880和3420你選哪個? 14 ///就不告訴你我之前寫的是小的,不然也不會把二維的寫出來啊,唉 15 int w[N],d[N],dp[N]; 16 17 int main() 18 { 19 int n,k,i,j; 20 21 while(scanf("%d%d", &n,&k) != EOF) 22 { 23 memset(dp,0,sizeof(dp));///清零清零 24 for(i=0;i<n;i++) 25 scanf("%d %d", &w[i], &d[i]); 26 27 for(i=0;i<n;i++) 28 for(j=k;j>=w[i];j--) 29 dp[j]=max(dp[j], dp[j-w[i]]+d[i]); 30 31 printf("%d\n", dp[k]); 32 } 33 return 0; 34 }
?