出现负数的01背包问题

把数位移一段值就可以了
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <vector>
 7 #define INF 0x3f3f3f3f
 8 #define mod 1000000007
 9 typedef long long LL;
10 using namespace std;
11 
12 const int maxw = 15000 + 10;
13 const int maxn = 25;
14 int n, m;
15 int dp[maxn][maxw];
16 int dis[maxn], wei[maxn];
17 
18 int main(int argc, const char * argv[]) {
19     scanf("%d%d", &n, &m);
20     for (int i = 1; i <= n; i++) {
21         scanf("%d", &dis[i]);
22     }
23     for (int i = 1; i <= m; i++) {
24         scanf("%d", &wei[i]);
25     }
26     dp[0][7500] = 1;
27     for (int i = 1; i <= m; i++) {
28         for (int j = 0; j <= 15000; j++) {
29             for (int k = 1; k <= n; k++) {
30                 dp[i][j + dis[k] * wei[i]] += dp[i - 1][j];
31             }
32         }
33     }
34     printf("%d
", dp[m][7500]);
35     return 0;
36 }
View Code
同样类型的还有POJ2184