内容发布更新时间 : 2024/12/27 6:01:18星期一 下面是文章的全部内容请认真阅读。
第6章课后作业结题报告
第一题：
给定n种物品和一个背包，物品i(1≤i≤n)的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：装入背包或者不装入背包。如何选择装入背包的物品，使得装入背包中物品的总价值最大？
这是一道老生常谈的背包问题，属于入门dp（Dynamic Programming动态规划）, 首先给出状态转移方程，设dp[i][j]表示用大小为j的背包去装前i个所能获得的最大价值, w[i]表示第i个物品的体积，v[i]表示第i个物品的价值。关于第i个物品的决策，就是间单的”取与不取”， 我们很容易得到如下的状态转移方程:
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
这边dp[i-1][j]表示第i个物品不取，dp[i-1][j-w[i]]+v[i]表示第i个物品取
因为每次推导只用的到i-1维，我们其实可以只用一维的滚动数组就可以来求解。这时候要逆序求解，这边不多做介绍
接下来是打印路径问题，这个需要逆序贪心打印。第i个背包是否选取应该用dp[i][V]与dp[i-1][V]来比较，从而求解，dp[i][V]>dp[i-1][V]，V表示当前可存在的最大容量。根据贪心，容量V越大价值同样装前i个一定更优，后面的推导的正解一定是基于dp[i][V]的，所以可以这么选
标程如下：
#include
for(i=n; i>=1; i--){
if(dp[i][k]!=dp[i-1][k]){ ans[i]=1; k=k-w[i];
} else{ } }
return; }
int main(){
int i, j, k;
scanf(\ for(i=1; i<=n; i++){
scanf(\ }
for(i=1; i<=n; i++){ for(j=1; j<=c; j++){ dp[i][j]=dp[i-1][j]; if(j>=w[i]){
dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i][j]); } } }
printf(\ print();
for(i=1; i<=n; i++) {
printf(\ }
return 0; }
第二题：
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组 Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。
这一题属于背包问题的变形
这首先转化为背包问题，如下: 如输入数据:
1 3 2 3 5 3
其实可以转化为: 体积分别为:
1 1 1 2 2 2 5 5 5, 价值都为1的物品，问题转化成问你物体的体积总和恰好为m时需要最小的价值数，
dp[i][j]表示前i个物品中抽取任意个恰好为m，所耗费的最少价值数
dp[i][j]=min(dp[i-1][j], dp[i-1][j-w[i]]+1);
但这边代码书写的时候要注意不是每个dp[i][j]的值都是可达到的，
即时任意一个数，不是你想凑就能凑出来的，所以这边要特判一下，先初始化为
足够大，如2000000000，然后在状态转移的时候都要先判断， 子问题是否已经被求解。
标程如下:
#include
using namespace std; int w[110], v[110]; int dp[110][20010]; int n, m; void init(){
for(int i=0; i<110; i++){
for(int j=0; j<20010; j++){ dp[i][j]=2000000000; } } }
int main(){
int i, j, k;
int t, x, cnt=1; scanf(\ for(i=1; i<=n; i++){
scanf(\ for(j=1; j<=x; j++){ w[cnt]=t;