动态规划-硬币重量最轻问题

Question

    设有n种不同面值的硬币，第i种硬币的币值是Vi(其中V1=1),重量是Wi,i=1,2，...n且现在购买某种总币值为y的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，那么如何选择付款的方法使得付出钱币的总重量最轻？使用动态规划设计策略设计一个求解该问题的算法。假设问题的输入实例是：

     V1=1， V2=4， V3=6， V4=8

     W1=1， W2=2，W3=4，W4=6

     Y=12

要求输出优化函数表和标记函数表、以及硬币支付方式。

最好用C语言

Answer 1

#include<stdio.h>
void strcpy(int *a, int *b, int Y){
    for(int i=0;i<=Y;i++) *(a+i) = *(b+i);
}
void solve(){
        int n; scanf("%d",&n);
        int type[n], weight[n], Y, i, j, k;
        for(i=0;i<n;i++) scanf("%d",&type[i]);
        for(i=0;i<n;i++) scanf("%d",&weight[i]);
        scanf("%d",&Y);
        int Min[Y+1], Min_Path[Y+1], path[n][Y+1];
        for(i=0;i<=Y;i++) Min[i] = 9999;
        Min[0] = 0;
        printf("\n");
        for(j=0;j<n;j++){
            for(i=type[j]; i<=Y; i++)
                if(Min[i] > Min[i-type[j]]+weight[j]){
                    Min_Path[i] = type[j];
                    Min[i] = Min[i-type[j]]+weight[j];
                }
            for(k=1;k<=Y;k++) printf("%-3d",Min[k]);
            printf("\n");
            strcpy(path[j],Min_Path,Y);
        }

        printf("\n");
        for(i=0;i<n;i++){
            for(j=1;j<=Y;j++)
                printf("%-3d",path[i][j]);
            printf("\n");
        }

        int y=Y;
        printf("\n支付方式:");
        while (y){
            printf("%d ",Min_Path[y]);
            y -= Min_Path[y];
        }
        printf("\n总重量:%d\n",Min[Y]);
}
int main(){
    solve();
    return 1;
}
/*
4
1 4 6 8
1 3 2 6
12
 */