动态编程代码大全（求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙）

本文目录

• 求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙
• 动态规划问题：用c++实现将一个整数分解成若干个整数的和，且这些整数都是2的k次方(k>=0)
• 求Python代码编动态规划贝尔曼函数
• 怎么用JAVA编程实现实时动态运行的模拟时钟
• Python之动态规划算法
• 动态规划求背包问题伪代码讲解

求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙

max Z=4x1+5x2 +6x3
s.t. 3x1+4x2+5x3《=10
x1,x2,x3》=0且都为整数
约束条件分析：
x1=1,2,3
x2=1,2
x3=1,2
阶段变量：x1、x2、x3
状态变量：
决策变量：
目标函数：Z=4x1+5x2 +6x3
状态转移方程：
约束条件用惩罚处理
……未完待续……

动态规划问题：用c++实现将一个整数分解成若干个整数的和，且这些整数都是2的k次方(k>=0)

动态规划转移方程：
a ,n是奇数
a ,n 是偶数
代码：
#include《iostream》
using namespace std;
__int64 a;
int flag(0);
int main()
{
a = 1;
a = 1;
a = 2;
while(cin》》n,n) //input integer n
{
for(int i=flag;i《=n;++i)
{
if(i&1) a%1000000000;
else a)%1000000000;
}
flag = n;
cout《《a《《endl;
}
return 0;
}
方程的想法有一点难以理解，其实你仔细想想也是可以理解的，需要细细琢磨

求Python代码编动态规划贝尔曼函数

class Node(object):
    def __init__(self, name):
        self._name = name
        self._value = None
        self._from = None
        self._next = 
    def setValue(self, value):
        self._value = value
    def setNext(self, node):
        self._next.append(node)
    def setFrom(self, node):
        self._from = node
    def getValue(self):
        return self._value
    def getNext(self):
        return self._next
    def getName(self):
        return self._name
    def getFrom(self):
        return self._from
    
class BFtree():
    def __init__(self, dList):
        self._dList = dList
    def bfValue(self, start):
        cur = start
        if cur.getNext() is not None:
            for node in cur.getNext():
                path = 
                path.sort()
                path = ’’.join(path)
                value = cur.getValue() + self._dList
                if node.getValue() is None or value 《 node.getValue():
                    node.setValue(value)
                    node.setFrom(cur)
                    self.bfValue(node)
    def move(self, start, end):
        print ’From: ’, start.getName(), ’ to: ’, end.getName()
        start.setValue(0)
        self.bfValue(start)
        trace = 
        cur = end
        while cur.getFrom() is not None:
            cur = cur.getFrom()
            trace.append(cur.getName())
        trace = reversed(trace)
        print ’The path is ’, ’ ’.join(trace),’ and the value is ’, end.getValue()
                
#builidng node
a = Node(’A’)
b = Node(’B’)
c = Node(’C’)
d = Node(’D’)
e = Node(’E’)
f = Node(’F’)
g = Node(’G’)
h = Node(’H’)
#build tree
a.setNext(b)
a.setNext(c)
a.setNext(d)
b.setNext(a)
b.setNext(g)
c.setNext(a)
c.setNext(g)
c.setNext(e)
d.setNext(a)
d.setNext(e)
e.setNext(c)
e.setNext(b)
e.setNext(f)
f.setNext(e)
g.setNext(b)
g.setNext(c)
g.setNext(h)
h.setNext(g)
#build distance list
dList = dict();
dList = 1
dList = 2
dList = 3
dList = 1
dList = 6
dList = 2
dList = 5
dList = 4
dList = 3
dList = 4
#build BFtree
tree = BFtree(dList)
tree.move(a,h)
tree.move(a,f)
tree.move(a,e)

代码略长....

怎么用JAVA编程实现实时动态运行的模拟时钟

import java.awt.*;
import java.applet.Applet;
import java.util.Calendar;
import java.text.SimpleDateFormat;
import java.util.Date;
public class ClockApplet extends Applet implements Runnable //Applet支持线程
{
private Thread athread; //线程
private SimpleDateFormat sdateformat; //日期格式
public void init()
{
this.setBackground(Color.white);//背景颜色设为白色
this.athread = null;
}
public void paint(Graphics g)
{
this.sdateformat = new SimpleDateFormat("hh时mm分ss秒");
g.drawString(this.sdateformat.format(new Date()),25,131);

Calendar rightnow = Calendar.getInstance();
int second = rightnow.get(Calendar.SECOND);
int minute = rightnow.get(Calendar.MINUTE);
int hour = rightnow.get(Calendar.HOUR);

//半径
int R_H = 20,R_M = 4,R_S = 4;
//时针的坐标
//x ====(9-3)
//y ====(12-6)
int H_x ;
int H_y;
//x
if(hour == 0)
{
hour = 12;
}
if( hour 》= 3 && hour 《= 9 )
{
H_x = R_H*Math.abs(hour - 9);
}
else
{
if(hour 》 9)
{
H_x = R_H*Math.abs(hour - 9);
}
else
{
H_x = R_H*Math.abs(hour+3);
}
}
//y
if( hour 》= 6 && hour 《= 12 )
{
H_y = R_H*Math.abs(hour - 12);
}
else
{
H_y = R_H*hour;
}

//分针的坐标
int M_x;
int M_y;

if(minute == 0)
{
minute = 60;
}
if( minute 》= 15 && minute 《= 45 )
{
M_x = R_M*Math.abs(minute - 45);
}
else
{
if(minute 》 45)
{
M_x = R_M*Math.abs(minute - 45);
}
else
{
M_x = R_M*Math.abs(minute+15);
}
}
//y
if( minute 》= 30 && minute 《 60 )
{
M_y = R_M*Math.abs(minute - 60);
}
else
{
M_y = R_M*minute;
}

//秒针的坐标
int S_x;
int S_y;

if(second == 0)
{
second = 60;
}
if( second 》= 15 && second 《= 45 )
{
S_x = R_S*Math.abs(second - 45);
}
else
{
if(second 》 45)
{
S_x = R_S*Math.abs(second - 45);
}
else
{
S_x = R_S*Math.abs(second+15);
}
}
//y
if( second 》= 30 && second 《= 60 )
{
S_y = R_S*Math.abs(second - 60);
}
else
{
S_y = R_S*second;
}
// g.drawString(String.valueOf(second),25,50);
// g.drawString(String.valueOf(minute),25,60);
// g.drawString(String.valueOf(hour),25,70);
// g.drawString(String.valueOf(H_x),25,80);
// g.drawString(String.valueOf(H_y),25,90);
g.drawOval(0,0,120,120);//距离相差10像素
g.setColor(Color.darkGray);
g.drawString("9",5,65);
g.drawString("3",110,65);
g.drawString("12",55,15);
g.drawString("6",55,115);

g.drawString("1",80,20);
g.drawString("2",100,40);
g.drawString("4",100,90);
g.drawString("5",80,110);

g.drawString("7",30,110);
g.drawString("8",10,90);
g.drawString("10",10,40);
g.drawString("11",30,20);

g.setColor(Color.red);
g.drawLine(60,60,H_x,H_y);//前一个点表示起点，另一个表示终点
g.setColor(Color.blue);
g.drawLine(60,60,M_x,M_y);
g.setColor(Color.yellow);
g.drawLine(60,60,S_x,S_y);
}
public void start()
{
if(athread == null)
{
athread = new Thread(this);
athread.start();
}
}
public void stop()
{
if(athread != null)
{
athread.interrupt();
athread = null;
}
}
public void run()
{
while(athread != null)
{
repaint();
try
{
athread.sleep(1000);
}
catch(InterruptedException e)
{
}
}
}
}

Python之动态规划算法

动态规划算法中是将复杂问题递归分解为子问题，通过解决这些子问题来解决复杂问题。与递归算法相比，动态编程减少了堆栈的使用，避免了重复的计算，效率得到显著提升。

先来看一个简单的例子，斐波那契数列.

斐波那契数列的定义如下。

斐波那契数列可以很容易地用递归算法实现：

上述代码，随着n的增加，计算量呈指数级增长，算法的时间复杂度是 。

采用动态规划算法，通过自下而上的计算数列的值，可以使算法复杂度减小到 ，代码如下。

下面我们再看一个复杂一些的例子。

这是小学奥数常见的硬币问题： 已知有1分，2分，5分三种硬币数量不限，用这些硬币凑成为n分钱，那么一共有多少种组合方法。

我们将硬币的种类用列表 coins 定义；
将问题定义为一个二维数组 dp，dp )凑成总价amt的组合数。

例如： coins =

dp 凑成总和为5的组合数。

对于所有的 dp 为1。

对于 dp 硬币总价amt的组合数，包含两种情况计算：

1.当使用第j个硬币时，有 dp 种情况，即amt减去第j个硬币币值，使用前j+1种硬币的组合数；

2.当不使用第j个硬币时，有 dp 种情况，即使用前j种硬币凑成amt的组合数；

所以： dp

我们最终得到的结果是：dp

上述分析省略了一些边界情况。

有了上述的分析，代码实现就比较简单了。

动态规划算法代码简洁，执行效率高。但是与递归算法相比，需要仔细考虑如何分解问题，动态规划代码与递归调用相比，较难理解。

我把递归算法实现的代码也附在下面。有兴趣的朋友可以比较一下两种算法的时间复杂度有多大差别。

上述代码在Python 3.7运行通过。

动态规划求背包问题伪代码讲解

开一个bool数组f，f表示是否可以用前i件物品【刚好】占用j的容量，初始化f[0..n
]=true。然后：
for i=1 to n
for j=w to s
f;
最后输出结果只需看f是否为true，为true则存在可行解，否则不存在。
输出解集的方法就是再开一个数组g，g记录当前位是选择了物品i还是没有选择物品i，这样完整的代码如下：
//DP
for i=1 to n
for j=w to s
if f==true
f=false;
else if f==true
f=true;
//output
j=s;i=n;
while i》=1
{
if g==true
输出物品i,j=j-w,i=i-1;
else
不用输出物品i,i=i-1;
}
不知道您能不能看懂，输出解集部分跟普通的01背包是一样的，建议您参考《背包九讲》，如果觉得我写的不清楚欢迎提问。希望能帮到您。