动态规划+背包问题 扩展
//商品购买方案 动态规划+背包问题
/*
int price[1000]; //每件商品的价格
int count[1000]; //每件商品买了多少件
int amount[1000][1000];
int num,row=0;
void dfs(int money,int n)
{
if(n>=num) //选择商品的种类超过规定的品种
return;
if(money <0) //剩余的钱不够买此商品
return;
if(money == 0) //满足这种购买方案
{
for(int i=0;i<num;i++)
amount[row][i] = count[i];
row++; //购买方案增加一种
}
else
{
count[n]++;
dfs(money-price[n],n); //继续购买本商品
count[n]--;
dfs(money,n+1); //购买下一种商品
}
}
void main()
{
int i,j;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d",&price[i]);
dfs(1000,0);
printf("%d\n",row);
for(i=0;i<row;i++)
{
for(j=0;j<num;j++)
printf("%d ",amount[i][j]);
printf("\n");
}
}*/
// n件商品，m的本件 每件商品价格 price[0],...price[n]，有多少种选择方案
//背包问题+动态规划 方法1
/*
int num,row=0; //多少种商品
int price[100];
int amount[1000][100];
int state[100]; //某种商品是否被购买，1为购买，0没有购买
void dfs(int money,int n)
{
if(n >=num)
return;
if(money<0)
return;
if(money == 0)
{
for(int i=0;i<num;i++)
amount[row][i] = state[i];
row++; //购买方案加1
}
else
{
for(int j=n;j<num;j++)
{
if(state[j])
break;
state[j] = 1;
dfs(money-price[j],n+1);
state[j] = 0;
}
}
}
void output()
{
int i,j;
for(i=0;i<row;i++)
{
for(j=0;j<num;j++)
if(amount[i][j])
printf("%d ",price[j]);
printf("\n");
}
}
void main()
{
int i;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d",&price[i]);
dfs(100,0); //本金100
output();
}*/
//n件商品，m的本件 每件商品价格 price[0],...price[n]，每种商品价值value[0]...value[n]有多少种选择方案
//动态规划+背包问题 方法2
/*
int num,row=0; //多少种商品
int price[100],value[100]; //每件商品价格和价值
int amount[1000][100];
int state[100]; //某种商品是否被购买，1为购买，0没有购买
int max=0,maxnum; //最大价值的方案
void dfs(int money,int n)
{
if(n >num)
return;
if(money<0)
return;
if(money == 0)
{
for(int i=0;i<num;i++)
amount[row][i] = state[i];
row++; //购买方案加1
}
else
{
state[n]=1; // 购买这个商品
dfs(money-price[n],n+1);
state[n]=0; //不购买这个商品，查看下一个商品
dfs(money,n+1);
}
}
void output() //输出方案的价值
{
int i,j;
for(i=0;i<row;i++)
{
int sum=0;
for(j=0;j<num;j++)
if(amount[i][j])
{printf("%d ",value[j]); sum+=value[j];}
if(sum >max)
{max= sum;maxnum=i+1;}
printf("\n");
}
printf("%d %d\n",maxnum,max);
}
void main()
{
int i;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d %d",&price[i],&value[i]);
dfs(100,0); //本金100
output();
}*/
//背包问题 + 动态规划
//n种商品，m的本金 每件商品价格 price[0],...price[n]，每件商品的数量count[0]...count[n];
/*
int num; //有多少种商品
int price[100]; //每件商品的价格
int count[100]; //每件商品的库存
int amount[100][100];
int qcount[100]; //每种商品取的数量
int row=0;
void dfs(int money,int n)
{
if(n>num) //取的商品种类大于商品的种类
return;
if(money <0) //钱不够买此种商品
return;
if(qcount[n] > count[n]) //这种商品没有货了
return;
if(money ==0)
{
for(int i=0;i<num;i++)
amount[row][i] = qcount[i];
row++;
}
else
{
qcount[n]++; //购买此商品
dfs(money-price[n],n); //继续购买这种商品
qcount[n]--;
dfs(money,n+1); //购买下一种商品
}
}
void output()
{
int i,j;
for(i=0;i<row;i++)
{
for(j=0;j<num;j++)
printf("%d ",amount[i][j]);
printf("\n");
}
}
void main()
{
int i;
scanf("%d",&num);
for(i=0;i<num;i++)
scanf("%d %d",&price[i],&count[i]); //设定每种商品价格和数量
dfs(1000,0);
output();
}*/
补充：综合编程 , 其他综合 ,
