我理解的背包類問題，大概有兩類：
(1) 在N組物品中，挑選出M個，使得某些性質最優。
(2) 在N組物品中，挑選出M個，求并符合某條件的方案數。
比較典型的有0-1背包，完全背包，多重背包，樹形背包等等...
這些問題，詳見
《背包九講》然后推薦一些例題：
poj 3093 分類：(2)
難度： 3
solution :
poj 3053
1 /*
2 先考慮將m個物品完全裝入容量c的背包的方案：
3 F(i,j) = F(i-1,j) + F(i-1,j-v[i])
4 然后O(n)枚舉剩下的最小的那個。
5 */
6 #include<iostream>
7 #include<cstdio>
8 #include<algorithm>
9 using namespace std;
10 typedef long long ll;
11 const int M = 1005;
12 const int N = 33;
13 ll dp[M][N], sum[N];
14 int main(){
15 int tst ; ll num[N]; cin >> tst;
16 for(int _ =1; _<=tst; _++){
17 int n,c;
18 cin >> n >> c;
19 for(int i = 1; i <= n; i++)
20 cin >> num[i];
21 sort(num+1,num+1+n);
22 for(int i = 1; i <= n; i++)
23 sum[i] = sum[i-1] + num[i];
24 ll ans = (sum[n] <= c);
25 for(int mn = 1; mn <= n; mn++) {
26 for(int j = 1; j <= c; j++)
27 dp[j][0] = 0;
28 for(int i = 0; i <= n; i++)
29 dp[0][i] = 1;
30 for(int i = 0; i <= c; i++)
31 for(int j = 1; j + mn <= n; j++){
32 dp[i][j] = dp[i][j-1];
33 if(i - num[j + mn] >= 0)
34 dp[i][j] += dp[i - num[j+mn]][j-1];
35 }
36 for(int i = 0; i <= c; i++){
37 ll mnt = c - i - sum[mn - 1] ;
38 if(mnt >= 0 && mnt < num[mn]){
39 if(i == 0 && mn == 1) continue;
40 ans += dp[i][n - mn];
41 }
42 }
43 }
44 cout<< _ <<" "<< ans <<endl;
45 }
46 }
47 分類：(2)
難度：3
hdu 2845分類：(1)
難度：1
solution:
hdu 2845
1 /*
2 對于線性序列來說， f(i) = max( f(i-1) , f(i-2) + v[i])
3 很容易擴展到2維
4 */
5
6 import java.util.*;
7 import java.io.*;
8
9 class Reader{
10
11 static BufferedReader reader;
12 static StringTokenizer tokenizer;
13
14 static void init(InputStream input){
15 reader = new BufferedReader(new InputStreamReader(input));
16 tokenizer = new StringTokenizer("");
17 }
18
19 static String next() throws IOException {
20 while(!tokenizer.hasMoreTokens()){
21 String ch = reader.readLine();
22 if(ch == null) return "-1";
23 tokenizer = new StringTokenizer(ch);
24
25 }
26 return tokenizer.nextToken();
27 }
28
29 static int nextInt() throws IOException { return Integer.parseInt(next());}
30
31 }
32
33
34 class pro_f{
35
36 private static int N = 200005;
37 private static ArrayList<Integer>[] num = new ArrayList [N];
38 private static int[] value = new int[N];
39 private static int[] tmp = new int[N];
40 public static void main(String args[]) throws IOException{
41 Reader.init(System.in);
42 // Scanner Reader = new Scanner(System.in);
43 for(int i = 0; i < N; i++) num[i] = new ArrayList<Integer>(0);
44 while(true){
45 int n = Reader.nextInt();
46 if(n == -1) break;
47 int m = Reader.nextInt();
48 for(int i = 0; i < n;i++) num[i].clear();
49 for(int i = 0; i < n; i++)
50 for(int j = 0; j < m; j++){
51 int val = Reader.nextInt();
52 // System.out.println(val);
53 num[i].add(val);
54 }
55 for(int i = 0; i < n; i++){
56 tmp[0] = num[i].get(0);
57 for(int j = 1; j < m; j++){
58 tmp[j] = tmp[j-1];
59 int val = (j == 1 ? 0 : tmp[j-2]) + num[i].get(j);
60 if(val > tmp[j]) tmp[j] = val;
61 }
62 value[i] = tmp[m-1];
63 }
64 tmp[0] = value[0];
65 for(int i = 1; i < n; i++){
66 tmp[i] = tmp[i-1];
67 int val = (i == 1 ? 0 : tmp[i-2]) + value[i];
68 tmp[i] = Math.max(tmp[i],val);
69 }
70 System.out.println(tmp[n-1]);
71 }
72 }
73
74 } cf 229E分類(1)
難度：2
solution:
http://m.shnenglu.com/hanfei19910905/archive/2012/10/03/192701.html
cf 145C分類(2)
難度：2
solution:
http://m.shnenglu.com/hanfei19910905/archive/2012/11/30/195844.html
cf 212E分類(2)
難度 2
solution:
http://m.shnenglu.com/hanfei19910905/archive/2012/07/21/184530.html
posted on 2012-12-03 13:40
西月弦 閱讀(462)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告