ccfcsp何以包邮?背包问题思路-创新互联
一个旅行者有一个最多能用M公斤的背包,现在有N件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为V1, V2,..., Vn. 若每种物品只有一件求旅行者能获得大总价值。 输入格式: M,N W1,V1 W2,V2 ...... 输出格式: X
10年的辉县网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。全网整合营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整辉县建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联公司从事“辉县网站设计”,“辉县网站推广”以来,每个客户项目都认真落实执行。动态规划解法1、定义二维数组dp[n+1][m+1] (数组行和列要大于n+1和m+1)。其中n表示物品数目,m表示当前重量上限。那么dp[2][3]表示在重量3的限制下,拿两个物品能得到大的重量。
注:为便于理解从1开始
2、初始化二维数组。为了减少时间复杂度,我们只需要初始化dp数组的第一行和第一列(dp[0][0]可以忽略,不会遍历它)。
for (int i = 1; i< m + 1; i++) //因为是从1开始 { dp[0][i] = 0; } for (int i = 1; i< n + 1; i++) { dp[i][0] = 0; }
原因是遍历dp的方向为从左到右,从上到下。故大值为右下角
3、不断记录在不同的n和m的情况。
for (int i = 1; i< n + 1; i++) { for (int j = 1; j< m + 1; j++) { if (a[i]<= j && dp[i - 1][j - a[i]] + a[i] >dp[i-1][j]) { dp[i][j] = dp[i - 1][j - a[i]] + a[i]; } else { dp[i][j] = dp[i - 1][j]; } }ccf csp何以包邮?
题目描述
新学期伊始,适逢顿顿书城有购书满 x 元包邮的活动,小 P 同学欣然前往准备买些参考书。 一番浏览后,小 P 初步筛选出 n 本书加入购物车中,其中第 i 本(1≤i≤n)的价格为 ai 元。 考虑到预算有限,在最终付款前小 P 决定再从购物车中删去几本书(也可以不删),使得剩余图书的价格总和 m 在满足包邮条件(m≥x)的前提下最小。
试帮助小 P 计算,最终选购哪些书可以在凑够 x 元包邮的前提下花费最小?
输入格式
从标准输入读入数据。
输入的第一行包含空格分隔的两个正整数 n 和 x,分别表示购物车中图书数量和包邮条件。
接下来输入 n 行,其中第 i 行(1≤i≤n)仅包含一个正整数 ai,表示购物车中第 i 本书的价格。输入数据保证 n 本书的价格总和不小于 x。
输出格式
输出到标准输出。
仅输出一个正整数,表示在满足包邮条件下的最小花费。
样例1输入
4 100 20 90 60 60
样例1输出
110
思路:由于该题没有固定的背包上限(求一定范围大问题),而只有一个包邮条件(求一定范围最小)。故我的思路是用一个min来作为‘背包上限’,min一开始是全部属的价格之和,当dp[i][j]大于x以及小于min时,改变min值,最后min是满足包邮条件下的最小花费。(只有95分)
# include# include int main() { int n, x, tmp=0, min =0, sum=0, j=0; scanf("%d %d", &n, &x); int* a = (int*)malloc(sizeof(int) * (n + 1)); for (int i = 1; i< n+1; i++) { scanf("%d", &a[i]); sum += a[i]; } int** dp = (int**)malloc(sizeof(int*) * (n+1)); for (int i = 0; i< n+1; i++) { dp[i] = (int*)malloc(sizeof(int) * (sum+1)); } //初始化dp数组 for (int i = 1; i< sum + 1; i++) { dp[0][i] = 0; } for (int i = 1; i< n + 1; i++) { dp[i][0] = 0; } min = sum; for (int i = 1; i< n + 1; i++) { for (int j = 1; j< min + 1; j++) { if (a[i]<= j && dp[i - 1][j - a[i]] + a[i] >dp[i-1][j]) { dp[i][j] = dp[i - 1][j - a[i]] + a[i]; if (dp[i][j] >= x && dp[i][j]< min) { min = dp[i][j]; //在dp[i][j]大于x以及小于min时,改变min值 } } else { dp[i][j] = dp[i - 1][j]; } } } printf("%d", min); return 0; }
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章名称:ccfcsp何以包邮?背包问题思路-创新互联
当前URL:http://pwwzsj.com/article/dsgphi.html