问题描述
- C/C++求纠正逻辑错误，01背包问题
-
原题如下：
公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入：
第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个1行，分别代表这m种商品的单价。
程序输出：
第一行是一个整数，表示共有多少种方案
第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
例如：
输入：
2
200
300
则应输出：
2
2 2
5 0
输入：
2
500
800
则应输出：
1
2 0我的代码:
#include"iostream"
using namespace std;
#define N 1000 //N存储总钱1000
int a[100],b[100][100]={0},n,p=1,q=1; //a数组存商品价格，b数组存商品数量 p,q为b数组下标
int dex[100]; //记录一种方案对应商品的数量
void DLS(int a[],int money)
{
int i,j;
for(i=1;i<=n;i++)
{
if((money+a[i])<=N)
{
if(N==(money+a[i])) //找到了一种方案；
{
dex[i]++;
for(j=1;j<=n;j++) //存一种方案下标
b[p][j]=dex[j];
p++;
}
else
{
money+=a[i];
dex[i]++;
DLS(a,money);
dex[i]--;
}}
}
}
int main()
{
int i=0,j;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
DLS(a,0);
cout<<p-1<<endl; //总共有多少个方案
for(i=1;i<p;i++)
{
for(j=1;j<=n;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
我想说的是。。这两个都不是我要的答案。。以下是我想使用回溯法推测，（如果推错了请指点）
输入 2
200
800
理论上应该有3中方案的。
1，200 200 200 200 200 200
2，200 800- 800 200
输入 2
200
300
理论上应该有5种答案，
1 200 200 200 200 200
2，200 200 300 300
3，200 300 200 300
4 300 200 200 300
5 300 300 200 200
请大牛指点
- 800 200
解决方案
首先，楼主给出的样例，
输入
2
200
800，
应该理论只有两种
5 0和
1 1。800+200和200+800是同一种购买方法。
就算法来说，楼主的程序会漏掉很多结果，而且有些结果还不正确，建议楼主自己Debug找一找问题，只有自己Debug才能理解问题出在何处。
#include "stdafx.h"
#include <iostream>
#define N 1000//N存储总钱1000
int a[100], b[100][100]= { 0 },m,p;//a数组存商品价格，b数组存最终结果，m为商品个数,p为结果个数
int dex[100];//临时记录商品数量
using std::cout;
using std::cin;
using std::endl;
void divide(int rest, int mi_index);
int _tmain(int argc, _TCHAR* argv[])
{
//输入
cin >> m;
for (int i = 0; i < m; i++)
cin >> a[i];
divide(N, 0);//计算
//输出
for (int j = 0; j < p; j++)
{
for (int i = 0; i < m; i++)
cout << b[j][i]<<" ";
cout << endl;
}
system("pause");
return 0;
}
void divide(int rest, int mi_index)
{
if (rest == 0)//剩余额度为零，记录结果到b[100][100]数组
{
for (int i = 0; i < mi_index; i++)
{
b[p][i] = dex[i];
}
p++;
}
else
if (rest>0)
if (mi_index == m - 1)//最后一件商品
{
if (rest%a[mi_index] == 0)//能整除记录结果，否则舍弃
{
for (int i = 0; i < mi_index; i++)
b[p][i] = dex[i];
b[p][mi_index] = rest / a[mi_index];
p++;
}
}
else//剩余额度为正，且不为最后一件商品
{
int possible = rest / a[mi_index];//此商品所有可能数量
for (int i = 0; i <= possible; i++)
{
dex[mi_index] = i;//临时记录此商品购买个数
divide(rest - i*a[mi_index], mi_index + 1);//扣除购买金额，计算下一件商品个数
}
}
}
输出样例
用楼主的程序输出如下图，希望楼主用此样例Debug找找问题。
解决方案二：
你的这个是要求次序也可以反过来么？
解决方案三：
在公司里，每年新员工入职都会回答楼主的类似的问题。但从来都没有标准答案，而且随着自己年龄的增加（10+程序员经验），自己的想法也在变化。
我就先当楼主是刚出校园的新同学来试着回答下。
先说下身边一起毕业的同学，在10年后，大家还在做什么（211重本毕业，毕业后就不从事IT研发的不在下面讨论重）？
1.依然还在程序员，以写代码为主，技术骨干。
2.做管理层，一般为小公司的CTO，技术总监，属于公司技术的带头人，同事也带领团队。
3.转为运营，做小公司的CEO，或者部门经理之类。完全不再编写代码。
4.创业，自己开公司，做APP或者独立工作者等。
5.外企，当前最滋润的，从来不加班。从来不认可IT的6*12文化和加班文化。
当年毕业的同学，大概有15人左右（占1半）毕业后从事IT研发工作，当前这15人基本都还在这个行业，只是职位变了很多。
大部分人经过10年的发展，都成为公司的技术骨干或者走上管理岗位。
那么，问题来了，是不是走上管理岗位的就一定好，做技术的就一定不好呢？
如果要从收入来看成功：
1.一直从事技术，并且从事管理的同学收入最高，比如CTO或者技术总监。
2.转作运营的，收入也不错。
3.创业的，失败的较多，非常成功（年收入100W+）还没有。
如果要从幸福指数来看成功：
1.内陆城市，比如成都的高于沿海，比如深圳，应该是消费较低，而收入和沿海差别不是特别大，所以算是性价比较高的地方。
2.创业的同学比上班的同学幸福指数高，做自己喜欢的事情，再苦再累也是最幸福的。