poj1741，POJ - 3624 Charm Bracelet

2023-10-18 阅读 24 评论 0

摘要：題目鏈接：http://poj.org/problem?id=3624 ? poj1741。題意：一共給出n種手鐲，每個手鐲有著各自的重量以及魅力值，在m重量下能得到的最大魅力值是多少。分析：標準的01背包。狀態轉移如此： dp[i][j]表示前i個手鐲在重量為j的背包

題目鏈接：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 }