付款的方法是的付出钱币的总重量最轻C语言

钱币的总重量最轻C语言"/>

付款的方法是的付出钱币的总重量最轻C语言

3.5 设有n种不同面值的硬币，第i种硬币的币值是vk(其中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

// Money.cpp : 定义控制台应用程序的入口点。
//
#include<iostream>
using namespace std;
#define MAX_NUM  20
int main()
{int weight[MAX_NUM] = { 0,1,2,4,6 };int value[MAX_NUM] = { 0,1,4,6,8 };int y = 12;  //凑出12元钱int n = 5;   //有5种硬币int F[MAX_NUM][MAX_NUM] = { 0 };int t[MAX_NUM][MAX_NUM] = { 0 };int i, j;//初始化for (int j = 1; j <= y; j++) {F[1][j] = j*weight[1];t[1][j] = 1;}//迭代更新for (int i = 2; i <= n; i++) {for (int j = 1; j <= y; j++) {F[i][j] = F[i - 1][j];t[i][j] = t[i - 1][j];if (F[i][j - value[i]] + weight[i] <= F[i - 1][j]) {F[i][j] = F[i][j] - value[i]] + weight[i];t[i][j] = i;}}}printf("钱币的总重量为：%d", F[5][12]);system("pause");
}