Cash Machine poj1276

编程与算法

这是以前在csdn写的博客，因为图太多就仅贴代码吧。如果想看图请移步：http://blog.csdn.net/anjicun/article/details/37772091

动态规划的题 第一次超时 修改后A过
//做好了图片 可以进行解释此题代码了
状态方程应该都没问题 fin[i] = max{fin[i],fin[i-w]+w}(w 为价值，fin[i] 表示 当价值为i 时 所能承载的最大价值 )
//下面这段代码是重点

1
2
3
4
5
6
7
8
9
10
while (k <= num){  
        for (int i = cash; i>= k*wei; i--){  
            fin[i] = max(fin[i],fin[i - k*wei] + k*wei);  
        }  
        num -= k;  
        k <<= 1;  
    }  
    for (int i = cash; i>=num * wei; i--){  
        fin[i] = max(fin[i],fin[i-num * wei] + num * wei);  
    }

下面 用 num = 6 cash = 10w 的例子来解释一下 请看动态图：
20140715102713728.gif

第一次循环(灰色) k = 1 < num = 6 fin[10w]~fin[1w] = w
第二次循环(桔色) k = 2 < num = 5 fin[10w]~fin[3w] = 3w fin[3w]~fin[2w] = 2w
第三次无法循环 k = 4 > num = 3 所以到下一段代码进行补充

for (int i = cash; i>=num * wei; i--)

状态方程 fin[i] = max{fin[i], fin[i-num*w]+num*w]} (num = 3,3w <= i <= 10w)
(黄色)fin[10w]~fin[6w] = 6w fin[6w]~fin[5w] = 5w ......
其实将 k <<= 1 换成 k++ 同样可以AC 道理是一样的 也同样可以证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>  
#include <string.h>  
#include <stdio.h>  
using namespace std;  
int cash;  
int Num;  
int fin[100001];  
int n[1001],w[1001];  
int max(int x,int y){  
        if(x>y)return x;  
        else return y;  
}  
void inpack(int num,int wei){  
        if(num*wei >= cash){  
                for(int i=wei;i<=cash;i++){  
                        //fin[i] = max(fin[i],fin[i-wei]+wei);  
                        fin[i] = (fin[i]>(fin[i-wei]+wei))?fin[i]:(fin[i-wei]+wei);  
                }  
                return;  
        }  
    int k = 1;  
    while (k <= num){  
        for (int i = cash; i>= k*wei; i--){  
            fin[i] = max(fin[i],fin[i - k*wei] + k*wei);  
        }  
        num -= k;  
        k <<= 1;  
    }  
    for (int i = cash; i>=num * wei; i--){  
        fin[i] = max(fin[i],fin[i-num * wei] + num * wei);  
    }  
}  
int main(){  
    int M,i;  
    while(scanf("%d%d",&cash,&M)!=EOF){  
        memset(fin,0,sizeof(fin));  
        for(i=1;i<=M;i++){  
            scanf("%d%d",&n[i],&w[i]);  
        }  
        for(i=1;i<=M;i++){  
            inpack(n[i],w[i]);  
        }  
        printf("%d\n",fin[cash]);  
    }  
    return 0;     
}