本文共 1626 字，大约阅读时间需要 5 分钟。
WA 了三次
1. solve_dp 中, 第一轮 把 cpmoney 写成了 money
2. 第二轮 dp 中, 把 +1 写成 +number[i]
3. T 的最大值设置出了问题
总结
1. 需要在纸上想好再动笔, 写这个代码的时候, solve_dp 的参数修改了若干次, 导致 WA 的次数过多
#include #include #include #include #include #include #include #include #include #include #define MIN(x,y) (x)<(y)?(x):(y)using namespace std;int money[200];int number[200];int dp[50000];int cpmoney[2000];int cpnumber[2000];int transTo01Pack(int n) { int newn = 0; for(int i = 0; i < n; i ++) { int num = number[i]; bool stop_flag = false; for(int j = 0; !stop_flag; j ++) { if(num - (1< = 0) { cpmoney[newn] = money[i]*(1< 0) { cpmoney[newn] = money[i] * num; cpnumber[newn] = num; newn ++; } } return newn;}int solve_dp(int cpn, int n, int cpt, int t) { memset(dp, 0x3f, sizeof(dp)); // first pass // 01 pack dp[0] = 0; for(int i = 0; i < cpn; i ++) { for(int v = cpt; v >= cpmoney[i]; v --) { dp[v] = min(dp[v], dp[v-cpmoney[i]] + cpnumber[i]); } } // second pass // complete pack for(int i = 0; i < n; i ++) { for(int v = cpt-money[i]; v >= 0; v --) { dp[v] = min(dp[v], dp[v+money[i]] + 1); } } if(dp[t] == 0x3f3F3F3F) return -1; return dp[t];}int main() { freopen("C:\\Users\\vincent\\Dropbox\\workplacce\\joj\\test.txt", "r", stdin); int N, T; while(scanf("%d%d", &N, &T) != EOF) { for(int i = 0; i < N; i ++) { scanf("%d", money+i); } for(int i = 0; i < N; i ++) { scanf("%d", number+i); } int cpn = transTo01Pack(N); int res = solve_dp(cpn, N, 50000, T); printf("%d\n", res); } return 0;}
转载于:https://www.cnblogs.com/zhouzhuo/p/3677109.html