http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=2574砝码称重
Description
设有1g 2g 3g 5g 10g 20g的砝码各若干枚（其总重<=1000），输出用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
Input
有多个测试数据
每个测试数据一行，由6个整数组成，分别是1g 2g 3g 5g 10g 20g砝码的数量
最后一行是0 0 0 0 0 0，不需要处理
Output
每组测试数据输出一行，输出总共可以称出的重量的数目。
Sample Input
1 1 1 1 1 1
0 0 0 0 0 0
Sample Output
41
Source
NOIP T96-4
问题分析：
把问题稍做一个改动，已知a1+a2+a3+a4+a5+a6个砝码的重量w[i]，w[i]∈{1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。
这样一改就是经典的0/1背包问题的简化版了，求解方法完全和上面说的一样，这里就不多说了，只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。
参考代码：
#include<iostream>
#include<cstdio>
using namespace std;
#include<memory.h>
#define MAXN 1010
int w[6]={1,2,3,5,10,20},a[6];
int dp[MAXN];
int main(void)
{
int i,j,k,sum,ans;
while(1)
{
sum=0;
for(i=0;i<6;i++)
{
scanf("%d",&a[i]);
sum+=w[i]*a[i];
}
if(!sum)
break;
//背包问题的核心代码
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=0;i<6;i++)
{
for(k=a[i];k>0;k--)
{
for(j=sum;j>=w[i];j--)
{
if(dp[j-w[i]])
dp[j]=1;
}
}
}
ans=0;
for(i=1;i<=sum;i++)
{
if(dp[i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
方法二：
f[i][j] 表示用1~i种砝码能否表示j这种面值，能为1，不能为0。
if(f[i-1][j]==1) f[i][j]=1;
for(k=1;k<=na[i];k++)
if(j-k*ma[i]==0||j-k*ma[i]>0 && f[i-1][j-k*ma[i]]==1)
{ f[i][j]=1;
break;
}
以上这是状态转移方程的代码。
然后，for(j=1;j<=max;j++)
if(f[6][j]==1)
sum++;
#include<iostream>
#include<cstdio>
using namespace std;
#include<memory.h>
#define MAXN 1010
int w[7]={0,1,2,3,5,10,20},a[6];
int dp[7][MAXN];
int main(void)
{
int i,j,k,sum,ans;
while(1)
{
sum=0;
for(i=1;i<=6;i++)
{
scanf("%d",&a[i]);
sum+=w[i]*a[i];
}
if(!sum)
break;
//背包问题的核心代码
memset(dp,0,sizeof(dp));
for(i=1;i<=6;i++)
{
for(j=1;j<=sum;j++)
{
if(dp[i-1][j] == 1)
dp[i][j] = 1;
else
{
for(k=1;k<=a[i];k++)
{
if(j-k*w[i] == 0 || (j-k*w[i] > 0 && dp[i-1][j-k*w[i]] == 1) )
{
dp[i][j]=1;
break;
}
}
}
}
}
ans=0;
for(i=1;i<=sum;i++)
{
if(dp[6][i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
另外一种写法：
#include<iostream>
#include<cstdio>
using namespace std;
#include<memory.h>
#define MAXN 1010
int w[7]={0,1,2,3,5,10,20},a[6];
int dp[7][MAXN];
int main(void)
{
int i,j,k,sum,ans;
while(1)
{
sum=0;
for(i=1;i<=6;i++)
{
scanf("%d",&a[i]);
sum+=w[i]*a[i];
}
if(!sum)
break;
//背包问题的核心代码
memset(dp,0,sizeof(dp));
for(j=1;j<=a[1];j++) //DP问题的初始化
dp[1][j*w[1]]=1;
for(i=2;i<=6;i++)
{
for(j=1;j<=sum;j++)
{
for(k=0;k<=a[i];k++) //多重背包比0-1背包多的循环：对砝码个数的控制
{
if(j-k*w[i] > 0 )
{
if(dp[i-1][j-k*w[i]] == 1)
dp[i][j]=1;
}
else if(j-k*w[i] == 0)
dp[i][j]=1;
}
}
}
ans=0;
for(i=1;i<=sum;i++)
{
if(dp[6][i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
状态转移方程 ：if(f[i-1][j-i1*b[i]]) f[i][j]=1; (0<=i1<=a[i],j-i1*b[i]>0)
if(j-i1*b[i]]==0) f[i][j]=1;
该题用动态规划解决的是统计问题。f[i][j]的值有两种，1和0，1代表用前i个砝码可以表示j这个重量，
状态转移思想：看前i-1个砝码是否可以 表示j这个重量，或者是否可以表示j-i1*b[i]这个重量 。i1代表砝码i的个数，b[i]代表i的重量。如果j-i1*b[i]==0，说明只用i砝码就可以称出j的重量，也将f[i][j]变为1。二、某种顺序下的01背包扩展题
http://acm.hdu.edu.cn/showproblem.php?pid=3466 Proud Merchants
因为剩余金额会对状态产生影响，所以应该先处理q-p较小的。这是一道01背包的变形题，题目增加了一个限制条件，即当你所拥有的钱数大于某个限定值时才可以购买该物品。
按照q - p以由小到大的顺序排序，然后进行01背包的DP即可。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 5001;
int f[MAX];
int V; //背包的体积
struct Node
{
int p,q,v;
}node[501];
void ZeroOnePack (int cost, int q,int weight)
{
int v;
for (v = V; v >= q; v--)
f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);
}
bool cmp(const Node &a,const Node &b)
{
return (a.q-a.p) < (b.q-b.p);
}
inline bool scan_d(int &num) // 这个就是 加速的 关键了
{
char in;bool IsN=false;
in=getchar();
if(in==EOF)
return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-') { IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
{
num*=10,num+=in-'0';
}
if(IsN)
num=-num;
return true;
}
int main(void)
{
int i,n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
V = m;
for(i = 0 ; i <= V ; ++i) //没有要求把背包装满
{
f[i]=0;
}
for(i = 1 ; i <= n ; ++i)
{
scan_d(node[i].p);
scan_d(node[i].q);
scan_d(node[i].v);
}
sort(node+1,node+n+1,cmp);
for(i = 1 ; i <= n ; ++i)
ZeroOnePack(node[i].p, node[i].q , node[i].v);
for(i = V ; i >= 0 ; --i)
{
if( f[i] )
{
printf("%d\n",f[i]);
break;
}
}
}
return 0;
}
分享到：
相关推荐
背包问题九讲，主要讲述经典背包问题和背包问题扩展
第一讲 01背包问题 这是最基本的背包问题，每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型，每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
0-1背包问题是经典的NP-HARD组合...首先对01背包问题及其解法进行了分析，然后提出01背包问题的两种扩展形式，并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。
背包问题的各种解法，以及背包问题的一些推导过程，再加上扩展的背包问题，很不错的教程
其次，利用一种新的区间编码映射机制，将差异演化算法扩展到求解离散领域优化问题。仿真实验结果表明，与其他进化算法相比，改进差异演化算法求解经典背包问题时，求解精度高，收敛速度快，是求解经典背包问题的一种...
背包问题具有多种变体和扩展，包括但不限于： 0-1背包问题：每种物品只有一件，可以选择放或不放。 完全背包问题：每种物品有无限件，可以选择放多件。 多重背包问题：每种物品有有限件。 这些问题在计算机科学、...
经典的01背包问题再加上它的扩展，肯定会让你的编程水平更上一层楼！
这是一个多维且有界的背包问题，属于常规0-1背包问题的扩展问题。 Input 第一行，物品的种类n，背包体积的限制V，背包载重量的限制W。n,V和W的范围如前所述。 接下来n行，每行为该种物品i的体积vi，重量wi，数量ci...
很多学校都会做的实验，计算机算法上一个很出名的东西，把几种排序方式都写进去了，如有需要，可以在此基础上做点修改扩展功能。
本文没有尝试对背包问题的本质进行扩展或深入挖掘，而只是从有限的理解（这里指对《背包问题九讲》的理解）出发，帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想，并通过实例解释了相应的...
该资源有背包问题的PPT，基础和扩展，训练题目
问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。 b. 回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度...
01背包问题动态规划资源。动态规划、回溯法、分支限界法。动态规划是一种通过将问题分解成更小的子问题来解决复杂问题的方法。它通常用于解决最优化问题，如最长公共子序列、最短路径等。动态规划的核心思想是将问题...
想去旅游吗？那得先准备背包！ 背包用来装旅游物品，现在共n种(n)旅游物品，每种物品都有体积vi，重量wi，数量ci，价值ti (vi,wi,ci和ti都为整数)。...这是一个多维且有界的背包问题，属于常规0-1背包问题的扩展问题。
0-1背包问题是经典的NP-HARD组合...首先对0-1背包问题及其解法进行了分析，然后提出0-1背包问题的两种扩展形式，并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。
一种可扩展延伸的背包的制作方法.docx
用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设r是当前剩余物品价值...
（点头像找对应文章里面详细教程+插件命令）↑↑↑ 重要↑↑↑
这是一个多维且有界的背包问题，属于常规0-1背包问题的扩展问题。 输入格式 第一行，物品的种类n，背包体积的限制V，背包载重量的限制W。n,V和W的范围如前所述。 接下来n行，每行为该种物品i的体积vi，重量wi，...
0-1背包问题是经典的组合优化问题与NP完全问题，具有重要的应用价值与...本文主要的贡献是将PAR方法推广到能处理带约束条件的组合优化类问题，大大扩展了PAR方法的应用范围，为形式化开发高效高可信组合优化类算法开