某企业每月给其A、B、C 和D 四个门店一共发送6 个集装箱的某种货物，如果各门店出售该种货物的利润(万元)如下表：
试求这6 箱货物如何分配给各门店，才能获得最大总利润。
解题思路：
将问题按卖场分为四个阶段，将A、B、C、D四个卖场分别编号为1、2、3、4。设：状态变量S：表示每月分配给第1个卖场至第4个卖场的货物吨数(k=1，2， 3，4)。
决策变量:表示每月分配给第1个卖场的货物吨数(k=1，2，3，4)。
状态转移方程为：Sk+1+Sk-Xk，即=Sk+1+Xk 。
已知S1=6，S4=X4。
dp(Sk)：表示第k阶段的最佳总效果。
r(xk)：表示第k阶段取得最佳效果时Xk的取值。
第一阶段
当K=1时
第二阶段
当K=2时
第三阶段
当K=3时
第四阶段
当K=4时
得到最优表开始逆推 依次取得4表中对应的最大值 r[3][6],r[2][5],r[1][2],r[0][2]
即最优解为A取2 B取2 C取1 D取1 即 6+4+3+4=17(万元)
public class liuzhuangSB {
public static int[][] s = new int[][] {{0,4,6,7,7,7,7},{0,2,4,6,8,9,10},{0,3,5,7,8,8,8},{0,4,5,6,6,6,6}};
//dp记录每次递推的最大值
//r记录每次最大值的情况
//0123行代表A AB ABC ABCD
public static int[][] dp = new int[4][7];
public static int[][] r = new int[4][7];
public static void main(String[] args) {
// TODO Auto-generated method stub
//将A赋值给最优情况
for(int i = 0; i < dp[0].length; i++) {
dp[0][i] = s[0][i];
r[0][i] = i;
}
//依次对AB ABC ABCD进行递推 得到所有的最优情况表
for(int z = 1; z < 4; z++) {
for(int i = 0; i < dp[0].length; i++) {
int[] temp = new int[7];
for(int j = 0; j <= i; j++) {
temp[j] = dp[z-1][i-j]+s[z][j];
if(temp[j] > dp[z][i]) {
dp[z][i] = temp[j];
r[z][i] = j;
}
}
}
}
//逆推
int num = 6;
int nums[] = new int[4];
while(num!=0) {
for(int i = 3; i >= 0; i--) {
nums[i] = r[i][num];
num -= nums[i];
}
}
System.out.println("取A:"+nums[0]+"个 取B:"+nums[1]+"个 取C:"+nums[2]+"个 取D:"+nums[3]+"个");
}
}