C#使用动态规划解决0-1背包问题实例分析资源-CSDN文库

版权申诉

16 浏览量 2020-12-31 22:13:06 上传评论 1 收藏 35KB PDF 举报

资源推荐

资源详情

资源评论

C#使用动态规划解决使用动态规划解决0-1背包问题实例分析背包问题实例分析

本文实例讲述了C#使用动态规划解决0-1背包问题的方法。分享给大家供大家参考。具体如下：

// 利用动态规划解决0-1背包问题

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Knapsack_problem

// 背包问题关键在于计算不超过背包的总容量的最大价值

{

class Program

{

static void Main()

{

int i;

int capacity = 16;

int[] size = new int[] { 3, 4, 7, 8, 9 };

// 5件物品每件大小分别为3, 4, 7, 8, 9

//且是不可分割的 0-1 背包问题

int[] values = new int[] { 4, 5, 10, 11, 13 };

// 5件物品每件的价值分别为4, 5, 10, 11, 13

int[] totval = new int[capacity + 1];

// 数组totval用来存贮最大的总价值

int[] best = new int[capacity + 1];

// best 存贮的是当前价值最高的物品

int n = values.Length;

for (int j = 0; j <= n - 1; j++)

for (i = 0; i <= capacity; i++)

if (i >= size[j])

if (totval[i] < (totval[i - size[j]] + values[j]))

// 如果当前的容量减去J的容量再加上J的价值比原来的价值大，

//就将这个值传给当前的值

{

totval[i] = totval[i - size[j]] + values[j];

best[i] = j; // 并把j传给best

}

Console.WriteLine("背包的最大价值: " + totval[capacity]);

// Console.WriteLine("构成背包的最大价值的物品是: " );

// int totcap = 0;

// while (totcap <= capacity)

// {

// Console.WriteLine("物品的大小是：" + size[best[capacity - totcap]]);

// for (i = 0; i <= n-1; i++)

// totcap += size[best[i]];

// }

}

}

}

希望本文所述对大家的C#程序设计有所帮助。

您可能感兴趣的文章您可能感兴趣的文章:用贪心法求解背包问题的解决方法关于背包问题的一些理解和应用PHP动态规划解决0-1背包问题实例分

析PHP回溯法解决0-1背包问题实例分析PHP贪婪算法解决0-1背包问题实例分析C++动态规划之背包问题解决方法C#使用回

溯法解决背包问题实例分析C#用递归算法解决经典背包问题

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

内容反馈

版权申诉

weixin_38569515

粉丝: 2
资源: 1001

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip